Paper:

# 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

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.14 No.4, pp. 408-415, 2010.

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