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

Abstract:

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.

References

[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.

Full-Text

comments powered by Disqus