Community detection
From InterSciWiki
There exists a vast literature in the social sciences about various definitions of such cohesive groups. See Wasserman and Faust: Social network analysis for an overview.
NetworksLiterature»Community Detection
new: V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. JSTAT, in press, 2008. http://arxiv.org/abs/0803.0476
new: J. Reichardt and S. Bornholdt. Clustering of sparse data via network communities - a prototype study of a large online market. J. Stat. Mech., page P06016, 2007.
new: "Algorithm finds the network-for genes" - J. Ruan and W. Zhang, Identifying network communities with a high resolution, Physical Review E, 77:016104, 2008.
missed: H. Zhou and R. Lipowsky. Network brownian motion: a new method to measure vertex-vertex proximity an to identify communities and subcommunities, pages 1062–1069. Springer- Verlag Berlin Heidelberg, 2004.
[edit] Modularity Q splitting or hierarchical clustering algorithm
One property of real world networks is their modular structure: certain groups of nodes are more densely interconnected internally than with the rest of the network. Often, they are referred to as "communities" or "cohesive subgroups" or simply "clusters". To find these is generally a hard combinatorial optimization problem. The "search space" is the set of all possible partitions of the network in groups, i.e. the set of all subsets, grows faster than exponential with the size of the network.
pre-print Community structure in social and biological networks, PNAS USA 99, 7821-7826 (2002)
Finding and evaluating community structure in networks, M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
Fast algorithm for detecting community structure in networks Newman 2004 preprint Phys. Rev, 2004, E 69, 066133.
Modularity and community structure in networks, M. E. J. Newman, Proc. Natl. Acad. Sci. USA 103, 8577-8582 (2006).
Finding Community Structure in Mega-scale Social Networks Ken Wakita, Toshiyuki Tsurumi 2007
A Normalized and a Hybrid Modularity Haifeng Du, Douglas R. White, Yike Ren, Shuzhuo Li
[edit] Evolution of Degree
very fast Newman 2007
[edit] Mixing Patterns and Community Structure
http://www-personal.umich.edu/~mejn/
Newman M E J, Girvan M. Mixing patterns and community structure in networks. Pastor S, Rubi J, Diaz-Guilera A. Statistical Mechanics of Complex Networks. Berlin: R. Springer, 2003.
[edit] Betweenness and Community Structure
preprint Newman and Girvin http://www.pnas.org/cgi/reprint/99/12/7821
[edit] Modularity Q agglomerative algorithm optimization
A. Clauset, "Finding local community structure in networks." Physical Review E 72, 026132 (2005).
A. Clauset, M. E. J. Newman and C. Moore, "Finding community structure in very large networks." Physical Review E 70, 066111 (2004).
Discovering Functional Communities in Dynamical Networks Authors: Cosma Rohilla Shalizi, Marcelo F. Camperi, Kristina Lisa Klinkner
Detection of Complex Networks Modularity by Dynamical Clustering Authors: S. Boccaletti, M. Ivanchenko, V. Latora, A. Pluchino, A. Rapisarda
Thermodynamics of Community Structure Authors: Claire P. Massen, Jonathan P. K. Doye]
[edit] Modularity Q Genetic algorithm optimization
［13］ Tasgin, M.,"Community Detection Model using Genetic Algorithm in Complex Networks and Its Application in Real-Life Networks", MS Thesis, Graduate Program in Computer Engineering, Bogazici University, 2005
[edit] Spin Glass
This (part of the) article is heavily biased towards the work of J. Reichardt. Pls. improve by adding more references and discussions. ;-) Joerg
After the paper by Girvan and Newman ("Community structure in social and biological networks", PNAS USA 99, 7821-7826 (2002) pre-print) quite some interest arose especially among physicists in the problem and there has been a surge of algorithms on how to detect communities.
An analogy to the magnetic systems known from physics, socalled spin glasses, can be used to solve the problem. Consider the links of the network as attractive couplings of spins and the missing links as repulsive couplings. Then search for the configuration in which minimizes the energy and you will find that the spins on densely connected nodes will align in the same direction while different, losely interconnected groups of spins will be oriented in different directions. With this technique, you can analyse systems of millions of nodes.
Here are some example applications:
Analysis of the energy landscape of a folding protein:
J. Reichardt and S. Bornholdt "Detecting fuzzy community structures in complex networks with a Potts model", Phys. Rev. Lett. 93, 218701 (2004) pre-print
Analysis of the interests of the bidders on eBay:
J. Reichardt and S. Bornholdt "Clustering of sparse data via network communities—a prototype study of a large online market", J. Stat. Mech. (2007) P06016, pre-print
An important problem using these techniques is that even completely random networks can be partitioned in a way that looks as if there were cohesive subgroups. This was first shown numerically by R. Guimera et al in "Modularity from Fluctuations in Random Graphs and Complex Networks", Phys. Rev. E 70, 025101 (2004) pre-print. However, the analytical estimates they present are inaccurate.
Here are some references on how to distinguisch between "true" and "spurious" modularity:
J. Reichardt and S. Bornholdt "Statistical Mechanics of Community Detection" Phys. Rev. E 74 (2006) 016110 pre-print
J. Reichardt and S. Bornholdt "When are networks truly modular?" Physica D 224(1-2) (2006) 20-26 pre-print
J. Reichardt and S. Bornholdt "Partitioning and modularity of graphs with arbitrary degree distribution" Physical Review E, 76(1) (2007) 015102 pre-print
[edit] Cluster overlap
“Improving the Clustering Capabilities of Consensus” 2006 Lecture Notes in Computer Science abstract “This paper introduces SOM as a clustering method to evaluate complex and uncertain knowledge in Consensus, a distributed security system for vulnerability testing; it proposes new metrics to evaluate the cohesion of every cluster, and also the cohesion between clusters; it applies unsupervised algorithms and validity metrics to a security data set; and it presents a method to obtain the best number of clusters regarding these new cohesion metrics: Intracohesion and Intercohesion factors.”
Moody and White 2003
[edit] See also
Structural cohesion -- Intercohesion -- Clique percolation -- Mark Newman -- Haifeng Du
( Community structure was absorbed into and now points to Community detection )
