Mathematical Model and Algorithm for Link Community Detection in Bipartite Networks

DOI: 10.4236/ajor.2015.55035   PDF   HTML   XML   3,473 Downloads   4,006 Views   Citations


In the past ten years, community detection in complex networks has attracted more and more attention of researchers. Communities often correspond to functional subunits in the complex systems. In complex network, a node community can be defined as a subgraph induced by a set of nodes, while a link community is a subgraph induced by a set of links. Although most researches pay more attention to identifying node communities in both unipartite and bipartite networks, some researchers have investigated the link community detection problem in unipartite networks. But current research pays little attention to the link community detection problem in bipartite networks. In this paper, we investigate the link community detection problem in bipartite networks, and formulate it into an integer programming model. We proposed a genetic algorithm for partition the bipartite network into overlapping link communities. Simulations are done on both artificial networks and real-world networks. The results show that the bipartite network can be efficiently partitioned into overlapping link communities by the genetic algorithm.

Share and Cite:

Li, Z. , Zhang, S. and Zhang, X. (2015) Mathematical Model and Algorithm for Link Community Detection in Bipartite Networks. American Journal of Operations Research, 5, 421-434. doi: 10.4236/ajor.2015.55035.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Albert, R. and Barabási, A.L. (2002) Statistical Mechanics of Complex Networks. Reviews of Modern Physics, 74, 47-97.
[2] Newman, M.E.J. (2003) The Structure and Function of Complex Networks. SIAM Review, 45, 167-256.
[3] Newman, M.E.J. and Girvan, M. (2004) Finding and Evaluating Community Structure in Networks. Physical Review E, 69, Article ID: 026113.
[4] Hu, Y., Chen, H., Zhang, P., Li, M., Di, Z. and Fan, Y. (2008) Comparative Definition of Community and Corresponding Identifying Algorithm. Physical Review E, 78, Article ID: 026121.
[5] Fortunato, S. (2010) Community Detection in Graph. Physics Reports, 486, 75-174.
[6] Newman, M.E.J. (2012) Communities, Modules and Large-Scale Structure in Networks. Nature Physics, 8, 25-31.
[7] Zhang, S., Jin, G., Zhang, X.S. and Chen, L. (2007) Discovering Functions and Revealing Mechanisms at Molecular Level from Biological Networks. Proteomics, 7, 2856-2869.
[8] Ahn, Y.Y., Bagrow, J.P. and Lehmann, S. (2010) Link Communities Reveal Multi-Scale Complexity in Networks. Nature, 466, 761-764.
[9] Evans, T.S. and Lambiotte, R. (2009) Line Graphs, Link Partitions and Overlapping Communities. Physical Review E, 80, Article ID: 016105.
[10] Evans, T.S. (2010) Clique Graphs and Overlapping Communities. Journal of Statistical Mechanics: Theory and Experiment, 12037.
[11] Evans, T.S. and Lambiotte, R. (2010) Line Graphs of Weighted Networks for Overlapping Communities. The European Physical Journal B, 77, 265-272.
[12] Li, Z., Zhang, X.S., Wang, R.S., Liu, H. and Zhang, S. (2013) Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm. PLoS ONE, 8, e83739.
[13] Zhang, S., Wang, R.S. and Zhang, X.S. (2007) Identification of Overlapping Community Structure in Complex Networks Using Fuzzy c-Means Clustering. Physica A, 374, 483-490.
[14] He, D.X., Liu, D., Zhang, W., Jin, D. and Yang, B. (2012) Discovering Link Communities in Complex Networks by Exploiting Link Dynamics. Journal of Statistical Mechanics, 2012, Article ID: P10015.
[15] Guimmerà, R., Sale-Pardo, M. and Nunes Amaral, L.A. (2007) Module Identification in Bipartite and Directed Networks. Physical Review E, 76, Article ID: 036102.
[16] Barber, M.J. (2007) Modularity and Community Detection in Bipartite Networks. Physical Review E, 76, Article ID: 066102.
[17] Zhan, W., Zhang, Z., Guan, J. and Zhou, S. (2011) Evolutionary Method for Finding Communities in Bipartite Networks. Physical Review E, 83, Article ID: 066120.
[18] Murata, T. and Ikeya, T. (2010) A New Modularity for Detecting One-to-Many Correspondence of Communities in Bipartite Networks. Advances in Complex Systems, 13, 19-31.
[19] Costa, A. and Hansen, P. (2014) A Locally Optimal Hierarchical Divisive Heuristic for Bipartite Modularity Maximization. Optimization Letters, 8, 903-917.
[20] Du, N., Wang, B., Wu, B. and Wang, Y. (2008) Overlapping Community Detection in Bipartite Networks. Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, Sydney, 9-12 December 2008, 176-179.
[21] Souam, F., AÏtelhadj, A. and Baba-Ali, R. (2013) Dual Modularity Optimization for Detecting Overlapping Communities in Bipartite Network. Knowledge and Information Systems, 40, 455-488.
[22] Zhang, Z.Y., Wang, Y. and Ahn, Y.Y. (2013) Overlapping Community Detection in Complex Network Using Symmetric Binary Matrix Factorization. Physical Review E, 87, Article ID: 062803.
[23] Zhang, Z.Y. and Ahn, Y.Y. (2015) Community Detection in Bipartite Networks Using Weighted Symmetric Binary Matrix Factorization. International Journal of Modern Physics C, 26, Article ID: 1550096.
[24] Freeman, L.C. (2003) Finding Social Groups: A Meta-Analysis of the Southern Women Data. In: Breiger, R., Carley, C. and Pattison, P., Eds., Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, National Research Council, The National Academies Press, Washington DC, 39-97.
[25] Chen, B.L., Chen, L., Zhou, S.R. and Xu, X.L. (2013) Detecting Community Structure in Bipartite Networks Based on Matrix Factorization. International Journal of Wireless and Mobile Computing, 6, 599-607.
[26] Liu, X. and Murata, T. (2010) An Efficient Algorithm for Optimizing Bipartite Modularity in Bipartite Networks. Journal of Advanced Computational Intelligence and Intelligent Informatics, 14, 408-415.
[27] Murata, T. (2009) Detecting Communities from Bipartite Networks Based on Bipartite Modularities. Proceedings of the 2009 International Conference on Computational Science and Engineering, Vancouver, 29-31 August 2009, 50-57.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.