All Title Author
Keywords Abstract

PLOS ONE  2014 

Community Structures in Bipartite Networks: A Dual-Projection Approach

DOI: 10.1371/journal.pone.0097823

Full-Text   Cite this paper   Add to My Lib


Identifying communities or clusters in networked systems has received much attention across the physical and social sciences. Most of this work focuses on single layer or one-mode networks, including social networks between people or hyperlinks between websites. Multilayer or multi-mode networks, such as affiliation networks linking people to organizations, receive much less attention in this literature. Common strategies for discovering the community structure of multi-mode networks identify the communities of each mode simultaneously. Here I show that this combined approach is ineffective at discovering community structures when there are an unequal number of communities between the modes of a multi-mode network. I propose a dual-projection alternative for detecting communities in multi-mode networks that overcomes this shortcoming. The evaluation of synthetic networks with known community structures reveals that the dual-projection approach outperforms the combined approach when there are a different number of communities in the various modes. At the same time, results show that the dual-projection approach is as effective as the combined strategy when the number of communities is the same between the modes.


[1]  Everett MG, Borgatti SP (2013) The dual-projection approach for two-mode networks. Social Networks 35: 204–210. doi: 10.1016/j.socnet.2012.05.004
[2]  Breiger RL (1974) The duality of persons and groups. Social forces 53: 181–190. doi: 10.1093/sf/53.2.181
[3]  Jensen K, Kristensen LM, Wells L (2007) Coloured Petri Nets and CPN Tools for modelling and validation of concurrent systems. International Journal on Software Tools for Technology Transfer 9: 213–254. doi: 10.1007/s10009-007-0038-x
[4]  Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Physical review E 69: 026113. doi: 10.1103/physreve.69.026113
[5]  Guimerà R, Sales-Pardo M, Amaral LAN (2007) Module identification in bipartite and directed networks. Physical Review E 76: 036102. doi: 10.1103/physreve.76.036102
[6]  Barber MJ (2007) Modularity and community detection in bipartite networks. Physical Review E 76: 066102. doi: 10.1103/physreve.76.066102
[7]  Porter MA, Onnela J-P, Mucha PJ (2009) Communities in networks. Notices of the AMS 56: 1082–1097.
[8]  Fortunato S (2010) Community detection in graphs. Physics Reports 486: 75–174. doi: 10.1016/j.physrep.2009.11.002
[9]  Melamed D, Breiger RL, West AJ (2013) Community structure in multi-mode networks: Applying an eigenspectrum approach. Connections 33: 18–23.
[10]  Zhang P, Wang J, Li X, Li M, Di Z, et al. (2008) Clustering coefficient and community structure of bipartite networks. Physica A: Statistical Mechanics and its Applications 387: 6869–6875. doi: 10.1016/j.physa.2008.09.006
[11]  Zhan W, Zhang Z, Guan J, Zhou S (2011) Evolutionary method for finding communities in bipartite networks. Physical Review E 83: 066120. doi: 10.1103/physreve.83.066120
[12]  Freeman LC (2003) Finding social groups: A meta-analysis of the southern women data. Dynamic social network modeling and analysis: 39–97.
[13]  Guimerà R, Uzzi B, Spiro J, Amaral LAN (2005) Team assembly mechanisms determine collaboration network structure and team performance. Science 308: 697–702. doi: 10.1126/science.1106340
[14]  Fararo TJ, Doreian P (1984) Tripartite structural analysis: Generalizing the Breiger-Wilson formalism. Social Networks 6: 141–175. doi: 10.1016/0378-8733(84)90015-7
[15]  Carley KM (2003) Dynamic network analysis. Dynamic social network modeling and analysis: Workshop summary and papers. Citeseer. 133–145.
[16]  Girvan M, Newman ME (2002) Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99: 7821–7826. doi: 10.1073/pnas.122653799
[17]  Newman ME (2006) Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103: 8577–8582. doi: 10.1073/pnas.0601602103
[18]  Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Physical review E 72: 027104. doi: 10.1103/physreve.72.027104
[19]  Pons P, Latapy M (2006) Computing communities in large networks using random walks. J Graph Algorithms Appl 10: 191–218. doi: 10.7155/jgaa.00124
[20]  Strehl A, Ghosh J (2003) Cluster ensembles–a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research 3: 583–617.
[21]  Reichardt J, Bornholdt S (2004) Detecting Fuzzy Community Structures in Complex Networks with a Potts Model. Phys Rev Lett 93: 218701 doi:10.1103/PhysRevLett.93.218701.
[22]  Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Computing Surveys (CSUR) 45: 43. doi: 10.1145/2501654.2501657
[23]  Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435: 814–818. doi: 10.1038/nature03607
[24]  Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics 11: 033015. doi: 10.1088/1367-2630/11/3/033015
[25]  Shen H, Cheng X, Cai K, Hu M-B (2009) Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and its Applications 388: 1706–1712. doi: 10.1016/j.physa.2008.12.021
[26]  Psorakis I, Roberts S, Ebden M, Sheldon B (2011) Overlapping community detection using bayesian non-negative matrix factorization. Physical Review E 83: 066114. doi: 10.1103/physreve.83.066114
[27]  Zhang S, Wang R-S, Zhang X-S (2007) Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications 374: 483–490. doi: 10.1016/j.physa.2006.07.023
[28]  Wang X, Jiao L, Wu J (2009) Adjusting from disjoint to overlapping community detection of complex networks. Physica A: Statistical Mechanics and its Applications 388: 5045–5056. doi: 10.1016/j.physa.2009.08.032
[29]  Murata T (2010) Detecting communities from tripartite networks. Proceedings of the 19th international conference on World wide web. ACM. 1159–1160.


comments powered by Disqus