HCS clustering algorithm - Revision history

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:56:19Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:56, 12 October 2024
Line 95:		Line 95:
	{{Reflist}}		{{Reflist}}

	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:23:31Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:23, 12 October 2024
Line 95:		Line 95:
	{{Reflist}}		{{Reflist}}

	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]

ErezHartuv at 14:45, 14 July 2024

2024-07-14T14:45:27Z

← Previous revision		Revision as of 14:45, 14 July 2024
Line 7:		Line 7:
	}}		}}

	The [https://www.researchgate.net/publication/222648006_A_clustering_algorithm_based_on_graph_connectivity '''HCS (Highly Connected Subgraphs) clustering algorithm''']<ref>{{Citation \| doi=10.1016/S0020-0190(00)00142-3\| title=A clustering algorithm based on graph connectivity \| year=2000 \| last1=Hartuv \| first1=E. \| last2=Shamir \| first2=R. \| journal=Information Processing Letters\| volume=76 \| issue=4–6 \| pages=175–181}}</ref> (also known as the '''HCS algorithm''', and other names such as '''Highly Connected Clusters/Components/Kernels''') is an algorithm based on graph connectivity for [[cluster analysis]]. It works by representing the similarity data in a [[similarity graph]], and then finding all the highly connected subgraphs. It does not make any prior assumptions on the number of the clusters. This algorithm was published by Erez Hartuv and [[Ron Shamir]] in 2000.		The [https://www.researchgate.net/publication/222648006_A_clustering_algorithm_based_on_graph_connectivity '''HCS (Highly Connected Subgraphs) clustering algorithm''']<ref>{{Citation \| doi=10.1016/S0020-0190(00)00142-3\| title=A clustering algorithm based on graph connectivity \| year=2000 \| last1=Hartuv \| first1=E. \| last2=Shamir \| first2=R. \| journal=Information Processing Letters\| volume=76 \| issue=4–6 \| pages=175–181}}</ref> (also known as the '''HCS algorithm''', and other names such as '''Highly Connected Clusters/Components/Kernels''') is an algorithm based on graph connectivity for [[cluster analysis]]. It works by representing the similarity data in a similarity graph, and then finding all the highly connected subgraphs. It does not make any prior assumptions on the number of the clusters. This algorithm was published by Erez Hartuv and [[Ron Shamir]] in 2000.

	The HCS algorithm gives a clustering solution, which is inherently meaningful in the application domain, since each solution cluster must have diameter 2 while a union of two solution clusters will have diameter 3.		The HCS algorithm gives a clustering solution, which is inherently meaningful in the application domain, since each solution cluster must have diameter 2 while a union of two solution clusters will have diameter 3.
Line 21:		Line 21:
	{{See also\|Connectivity (graph_theory)}}		{{See also\|Connectivity (graph_theory)}}

	HCS clustering algorithm finds all the subgraphs with n vertices such that the minimum cut of those subgraphs contain more than n/2 edges, and identifies them as clusters. Such a subgraph is called a [[Highly Connected Subgraph]] (HCS). Single vertices are not considered clusters and are grouped into a singletons set S.		HCS clustering algorithm finds all the subgraphs with n vertices such that the minimum cut of those subgraphs contain more than n/2 edges, and identifies them as clusters. Such a subgraph is called a Highly Connected Subgraph (HCS). Single vertices are not considered clusters and are grouped into a singletons set S.

	{{See also\|Minimum cut}}		{{See also\|Minimum cut}}

Frap at 10:10, 3 November 2022

2022-11-03T10:10:10Z

← Previous revision		Revision as of 10:10, 3 November 2022
Line 83:		Line 83:
	* [https://www.researchgate.net/publication/12446298_An_Algorithm_for_Clustering_cDNA_Fingerprints Gene expression analysis]<ref>		* [https://www.researchgate.net/publication/12446298_An_Algorithm_for_Clustering_cDNA_Fingerprints Gene expression analysis]<ref>
	E Hartuv, A O Schmitt, J Lange, S Meier-Ewert, H Lehrach, R Shamir. "An algorithm for clustering cDNA fingerprints." Genomics 66, no. 3 (2000): 249-256.</ref> The hybridization of synthetic oligonucleotides to arrayed cDNAs yields a fingerprint for each cDNA clone. Run HCS algorithm on these fingerprints can identify clones corresponding to the same gene.		E Hartuv, A O Schmitt, J Lange, S Meier-Ewert, H Lehrach, R Shamir. "An algorithm for clustering cDNA fingerprints." Genomics 66, no. 3 (2000): 249-256.</ref> The hybridization of synthetic oligonucleotides to arrayed cDNAs yields a fingerprint for each cDNA clone. Run HCS algorithm on these fingerprints can identify clones corresponding to the same gene.

	* [http://www.cs.utoronto.ca/~natasha/book_chpt5_GT_NP.pdf PPI network structure discovery]<ref>Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.</ref> Using HCS clustering to detect dense subnetworks in PPI that may have biological meaning and represent biological processes.		* [http://www.cs.utoronto.ca/~natasha/book_chpt5_GT_NP.pdf PPI network structure discovery]<ref>Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.</ref> Using HCS clustering to detect dense subnetworks in PPI that may have biological meaning and represent biological processes.
	* "Survey of clustering algorithms." Neural Networks, IEEE Transactions <ref>Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.</ref>		* "Survey of clustering algorithms." Neural Networks, IEEE Transactions <ref>Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.</ref>
Line 90:		Line 89:
	year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\|author4-link=Rolf Niedermeier\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|		year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\|author4-link=Rolf Niedermeier\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|
	doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>		doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>

	* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R Implementation]		* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R Implementation]
	* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Implementation]		* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Implementation]


	== References ==		== References ==

ErezHartuv at 17:14, 5 September 2022

2022-09-05T17:14:48Z

← Previous revision		Revision as of 17:14, 5 September 2022
Line 92:		Line 92:

	* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R Implementation]		* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R Implementation]

	* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Implementation]		* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Implementation]


	== References ==		== References ==

ErezHartuv at 17:02, 5 September 2022

2022-09-05T17:02:35Z

← Previous revision		Revision as of 17:02, 5 September 2022
Line 91:		Line 91:
	doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>		doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>

	* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R ~~Documentation~~]		* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R Implementation]

	* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python ~~Documentation~~]		* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Implementation]

	== References ==		== References ==

ErezHartuv at 17:01, 5 September 2022

2022-09-05T17:01:51Z

← Previous revision		Revision as of 17:01, 5 September 2022
Line 91:		Line 91:
	doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>		doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>

	* [~~http~~://~~svitsrv25~~.~~epfl~~.ch/~~R-doc/library~~/RBGL/~~html~~/~~highlyConnSG~~.~~html~~ R Documentation]		* [https://www.rdocumentation.org/packages/RBGL/versions/1.48.1/topics/highlyConnSG R Documentation]

	* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Documentation]		* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Documentation]

ErezHartuv at 16:54, 5 September 2022

2022-09-05T16:54:28Z

← Previous revision		Revision as of 16:54, 5 September 2022
Line 92:		Line 92:

	* [http://svitsrv25.epfl.ch/R-doc/library/RBGL/html/highlyConnSG.html R Documentation]		* [http://svitsrv25.epfl.ch/R-doc/library/RBGL/html/highlyConnSG.html R Documentation]

			* [https://github.com/53RT/Highly-Connected-Subgraphs-Clustering-HCS Python Documentation]

	== References ==		== References ==

Luamssuk: /* Examples of HCS usage */ author link Rolf Niedermeier

2022-05-22T14:14:23Z

Examples of HCS usage: author link Rolf Niedermeier

← Previous revision		Revision as of 14:14, 22 May 2022
Line 88:		Line 88:
	* The CLICK clustering algorithm<ref>{{Citation \| title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis \| year=2000 \| last1=Sharan \| first1=R. \| last2=Shamir \| first2=R. \| journal=Proceedings ISMB '00\| volume=8 \| pages=307–316C\| pmid=10977092 }}</ref> is an adaptation of HCS algorithm on weighted similarity graphs, where the weight is assigned with a probability flavor.		* The CLICK clustering algorithm<ref>{{Citation \| title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis \| year=2000 \| last1=Sharan \| first1=R. \| last2=Shamir \| first2=R. \| journal=Proceedings ISMB '00\| volume=8 \| pages=307–316C\| pmid=10977092 }}</ref> is an adaptation of HCS algorithm on weighted similarity graphs, where the weight is assigned with a probability flavor.
	* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage]<ref>{{Citation \|		* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage]<ref>{{Citation \|
	year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|		year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\|author4-link=Rolf Niedermeier\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|
	doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>		doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>

Citation bot: Add: s2cid, pmid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

2021-11-15T05:10:43Z

Add: s2cid, pmid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

← Previous revision		Revision as of 05:10, 15 November 2021
Line 86:		Line 86:
	* [http://www.cs.utoronto.ca/~natasha/book_chpt5_GT_NP.pdf PPI network structure discovery]<ref>Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.</ref> Using HCS clustering to detect dense subnetworks in PPI that may have biological meaning and represent biological processes.		* [http://www.cs.utoronto.ca/~natasha/book_chpt5_GT_NP.pdf PPI network structure discovery]<ref>Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.</ref> Using HCS clustering to detect dense subnetworks in PPI that may have biological meaning and represent biological processes.
	* "Survey of clustering algorithms." Neural Networks, IEEE Transactions <ref>Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.</ref>		* "Survey of clustering algorithms." Neural Networks, IEEE Transactions <ref>Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.</ref>
	* The CLICK clustering algorithm<ref>{{Citation \| title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis \| year=2000 \| last1=Sharan \| first1=R. \| last2=Shamir \| first2=R. \| journal=Proceedings ISMB '00\| volume=8 \| pages=307–316C}}</ref> is an adaptation of HCS algorithm on weighted similarity graphs, where the weight is assigned with a probability flavor.		* The CLICK clustering algorithm<ref>{{Citation \| title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis \| year=2000 \| last1=Sharan \| first1=R. \| last2=Shamir \| first2=R. \| journal=Proceedings ISMB '00\| volume=8 \| pages=307–316C\| pmid=10977092 }}</ref> is an adaptation of HCS algorithm on weighted similarity graphs, where the weight is assigned with a probability flavor.
	* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage]<ref>{{Citation \|		* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage]<ref>{{Citation \|
	year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|		year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|
	doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 }}</ref>		doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>

	* [http://svitsrv25.epfl.ch/R-doc/library/RBGL/html/highlyConnSG.html R Documentation]		* [http://svitsrv25.epfl.ch/R-doc/library/RBGL/html/highlyConnSG.html R Documentation]

← Previous revision		Revision as of 14:14, 22 May 2022
Line 88:		Line 88:
	* The CLICK clustering algorithm<ref>{{Citation \| title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis \| year=2000 \| last1=Sharan \| first1=R. \| last2=Shamir \| first2=R. \| journal=Proceedings ISMB '00\| volume=8 \| pages=307–316C\| pmid=10977092 }}</ref> is an adaptation of HCS algorithm on weighted similarity graphs, where the weight is assigned with a probability flavor.		* The CLICK clustering algorithm<ref>{{Citation \| title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis \| year=2000 \| last1=Sharan \| first1=R. \| last2=Shamir \| first2=R. \| journal=Proceedings ISMB '00\| volume=8 \| pages=307–316C\| pmid=10977092 }}</ref> is an adaptation of HCS algorithm on weighted similarity graphs, where the weight is assigned with a probability flavor.
	* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage]<ref>{{Citation \|		* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage]<ref>{{Citation \|
	year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|		year=2014 \| last1=Huffner \| first1=F. \| last2=Komusiewicz\| first2=C. \|last3=Liebtrau\|first3=A\|last4=Niedermeier\|first4=R\|author4-link=Rolf Niedermeier\| journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics\| volume=11\| issue=3 \| pages=455–467\|
	doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>		doi=10.1109/TCBB.2013.177\| pmid=26356014 \| title=Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage\| citeseerx=10.1.1.377.1900 \| s2cid=991687 }}</ref>