An Efficient Algorithm for Optimizing Bipartite Modularity in Bipartite Networks

Xin Liu; Tsuyoshi Murata

doi:10.20965/jaciii.2010.p0408

single-jc.php

« previous

JACIII Vol.14 No.4 pp. 408-415

doi: 10.20965/jaciii.2010.p0408

(2010)

Paper:

Views over last 60 days: 1,583

An Efficient Algorithm for Optimizing Bipartite Modularity in Bipartite Networks

Xin Liu and Tsuyoshi Murata

Graduate School of Information Science and Engineering, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro, Tokyo 152-8552, Japan

Received:

December 7, 2009

Accepted:

March 29, 2010

Published:

May 20, 2010

Keywords:

community detection, modularity, bipartite network, graph partitioning, link mining

Abstract

Modularity evaluates the quality of a division of network nodes into communities, and modularity optimization is the most widely used class of methods for detecting communities in networks. In bipartite networks, there are correspondingly bipartite modularity and bipartite modularity optimization. LPAb, a very fast label propagation algorithm based on bipartite modularity optimization, tends to become stuck in poor local maxima, yielding suboptimal community divisions with low bipartite modularity. We therefore propose LPAb+, a hybrid algorithm combining modified LPAb, or LPAb’, and MSG, a multistep greedy agglomerative algorithm, with the objective of using MSG to drive LPAb out of local maxima. We use four commonly used real-world bipartite networks to demonstrate LPAb+ capability in detecting community divisions with remarkably higher bipartite modularity than LPAb. We show how LPAb+ outperforms other bipartite modularity optimization algorithms, without compromising speed.

Cite this article as:

X. Liu and T. Murata, “An Efficient Algorithm for Optimizing Bipartite Modularity in Bipartite Networks,” J. Adv. Comput. Intell. Intell. Inform., Vol.14 No.4, pp. 408-415, 2010.

Data files:

References

[1] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E 69 026113, 2004.
[2] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, “Graph structure in the Web,” Computer Networks, Vol.33, pp. 309-320, 2000.
[3] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. USA 99, pp. 7821-7826, 2002.
[4] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, Vol.435, No.7043, pp. 814-818, 2005.
[5] N. Gulbahce and S. Lehmann, “The art of community detection, BioEssays,” Vol.30, No.10, pp. 934-938, 2008.
[6] A. Arenas, A. Díaz-Guilera, and C. J. Pérez-Vicente, “Synchronization reveals topological scales in complex networks,” Phys. Rev. Lett. 96, 114102, 2006.
[7] J. G. Restrepo, E. Ott, and B. R. Hunt, “Characterizing the dynamical importance of network nodes and links,” Phys. Rev. Lett. 97, 094102, 2006.
[8] M. E. J. Newman, “Modularity and community structure in networks,” Proc. Natl. Acad. Sci. USA 103, pp. 8577-8582, 2006.
[9] L. Danon, A. D.- Guilera, J. Duch, and A. Arenas, “Comparing community structure identification,” J. Stat. Mech. P09008, 2005.
[10] S. Fortunato, “Community detection in graphs,” Physics Reports, Vol.486, pp. 75-174, 2010.
[11] M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E 69, 066133, 2004.
[12] R. Guimerà, M. S.- Pardo, and L. A. N. Amaral, “Module identification in bipartite and directed networks,” Phys. Rev. E 76, 036102, 2007.
[13] M. J. Barber, “Modularity and community detection in bipartite network,” Phys. Rev. E 76, 066102, 2007.
[14] T. Murata and T. Ikeya, “A new modularity for detecting one-to-many correspondence of communities in bipartite networks,” Advances in Complex Systems, Vol.13, No.1, pp. 19-31, 2010.
[15] K. Suzuki and K. Wakita, “Extracting Multi-facet Community Structure from Bipartite Networks,” Proc. of 2009 Int. Conf. on Computational Science and Engineering (CSE 09), Vol.4, pp. 312-319, August 2009.
[16] S. Lehmann, M. Schwartz, and L. K Hansen, “Biclique communities,” Phys. Rev. E 78, 016108, 2008.
[17] N. Du, B. Wang, B. Wu, and Y. Wang, “Overlapping community detection in bipartite networks, Proc. of the 2008 IEEE/WIC/ACM Int. Conf. on Web Intelligence and Intelligent Agent Technology (WI-IAT 08), Vol.1, pp. 176-179, December 2008.
[18] X. Liu and T.Murata, “Community detection in large-scale bipartite networks,” Proc. of the 2009 IEEE/WIC/ACM Int. Conf. on Web Intelligence and Intelligent Agent Technology (WI-IAT 09), Vol.1, pp. 50-57, September 2009.
[19] R. Ghosh and K. Lerman, “Structure of Heterogeneous Networks,” arXiv:0906.2212, 2009.
[20] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E 76, 036106, 2007.
[21] M. J. Barber and J. W. Clark, “Detecting network communities by propagating labels under constraints,” Phys. Rev. E 80, 026129, 2009.
[22] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikolski, and D. Wagner, “On modularity – np-completeness and beyond,”
URL: http://i11www.iti.uni-karlsruhe.de/extra/publications/bdgghnwomnpcb-06.pdf, 2006.
[23] P. Schuetz and A. Caflisch, “Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement,” Phys. Rev. E 77, 046112, 2008.
[24] P. Schuetz and A. Caflisch, “Multistep greedy algorithm identifies community structure in real-world and computer-generated networks,” Phys. Rev. E 78, 026112, 2008.
[25] I. X. Y. Leung, P. Hui, P. Liò, and J. Crowcroft, “Towards real-time community detection in large networks,” Phys. Rev. E 79, 066107, 2009.
[26] A. Davis, B. B. Gardner, and M. R. Gardner, “Deep South,” University of Chicago Press, 1941.
[27] J. Scott and M. Hughes, “The anatomy of Scottish capital: Scottish companies and Scottish capital,” pp. 1900-1979, Croom Helm, London, 1980.
[28] M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Phys. Rev. E 74, 036104, 2006.
[29] A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Phys. Rev. E 70, 066111, 2004.
[30] B. H. Good and Y.- A. Montjoye, and A. Clauset, “The performance of modularity maximization in practical contexts,” Phys. Rev. E 81, 046106, 2010.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E 69 026113, 2004.

[2] [2] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, “Graph structure in the Web,” Computer Networks, Vol.33, pp. 309-320, 2000.

[3] [3] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. USA 99, pp. 7821-7826, 2002.

[4] [4] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, Vol.435, No.7043, pp. 814-818, 2005.

[5] [5] N. Gulbahce and S. Lehmann, “The art of community detection, BioEssays,” Vol.30, No.10, pp. 934-938, 2008.

[6] [6] A. Arenas, A. Díaz-Guilera, and C. J. Pérez-Vicente, “Synchronization reveals topological scales in complex networks,” Phys. Rev. Lett. 96, 114102, 2006.

[7] [7] J. G. Restrepo, E. Ott, and B. R. Hunt, “Characterizing the dynamical importance of network nodes and links,” Phys. Rev. Lett. 97, 094102, 2006.

[8] [8] M. E. J. Newman, “Modularity and community structure in networks,” Proc. Natl. Acad. Sci. USA 103, pp. 8577-8582, 2006.

[9] [9] L. Danon, A. D.- Guilera, J. Duch, and A. Arenas, “Comparing community structure identification,” J. Stat. Mech. P09008, 2005.

[10] [10] S. Fortunato, “Community detection in graphs,” Physics Reports, Vol.486, pp. 75-174, 2010.

[11] [11] M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E 69, 066133, 2004.

[12] [12] R. Guimerà, M. S.- Pardo, and L. A. N. Amaral, “Module identification in bipartite and directed networks,” Phys. Rev. E 76, 036102, 2007.

[13] [13] M. J. Barber, “Modularity and community detection in bipartite network,” Phys. Rev. E 76, 066102, 2007.

[14] [14] T. Murata and T. Ikeya, “A new modularity for detecting one-to-many correspondence of communities in bipartite networks,” Advances in Complex Systems, Vol.13, No.1, pp. 19-31, 2010.

[15] [15] K. Suzuki and K. Wakita, “Extracting Multi-facet Community Structure from Bipartite Networks,” Proc. of 2009 Int. Conf. on Computational Science and Engineering (CSE 09), Vol.4, pp. 312-319, August 2009.

[16] [16] S. Lehmann, M. Schwartz, and L. K Hansen, “Biclique communities,” Phys. Rev. E 78, 016108, 2008.

[17] [17] N. Du, B. Wang, B. Wu, and Y. Wang, “Overlapping community detection in bipartite networks, Proc. of the 2008 IEEE/WIC/ACM Int. Conf. on Web Intelligence and Intelligent Agent Technology (WI-IAT 08), Vol.1, pp. 176-179, December 2008.

[18] [18] X. Liu and T.Murata, “Community detection in large-scale bipartite networks,” Proc. of the 2009 IEEE/WIC/ACM Int. Conf. on Web Intelligence and Intelligent Agent Technology (WI-IAT 09), Vol.1, pp. 50-57, September 2009.

[19] [19] R. Ghosh and K. Lerman, “Structure of Heterogeneous Networks,” arXiv:0906.2212, 2009.

[20] [20] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E 76, 036106, 2007.

[21] [21] M. J. Barber and J. W. Clark, “Detecting network communities by propagating labels under constraints,” Phys. Rev. E 80, 026129, 2009.

[22] [22] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikolski, and D. Wagner, “On modularity – np-completeness and beyond,”
URL: http://i11www.iti.uni-karlsruhe.de/extra/publications/bdgghnwomnpcb-06.pdf, 2006.

[23] [23] P. Schuetz and A. Caflisch, “Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement,” Phys. Rev. E 77, 046112, 2008.

[24] [24] P. Schuetz and A. Caflisch, “Multistep greedy algorithm identifies community structure in real-world and computer-generated networks,” Phys. Rev. E 78, 026112, 2008.

[25] [25] I. X. Y. Leung, P. Hui, P. Liò, and J. Crowcroft, “Towards real-time community detection in large networks,” Phys. Rev. E 79, 066107, 2009.

[26] [26] A. Davis, B. B. Gardner, and M. R. Gardner, “Deep South,” University of Chicago Press, 1941.

[27] [27] J. Scott and M. Hughes, “The anatomy of Scottish capital: Scottish companies and Scottish capital,” pp. 1900-1979, Croom Helm, London, 1980.

[28] [28] M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Phys. Rev. E 74, 036104, 2006.

[29] [29] A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Phys. Rev. E 70, 066111, 2004.

[30] [30] B. H. Good and Y.- A. Montjoye, and A. Clauset, “The performance of modularity maximization in practical contexts,” Phys. Rev. E 81, 046106, 2010.