Dual modularity optimization for detecting overlapping communities in bipartite networks
Tóm tắt
Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.
Tài liệu tham khảo
Aïtelhadj A, Boughanem M, Mezghiche M, Souam F (2012) Using structural similarity for clustering XML documents. Knowl Inf Syst 32(1):109–139
Baumes J, Goldberg M, Magdon-Ismail M (2005) Efficient identification of overlapping communities. In: Proceeding of the IEEE international conference on intelligence and security informatics ISI 2005. LNCS, vol 3495. Springer, Heidelberg, pp 27–36. http://citeseerx.ist.psu.edu/viewdoc/summary? doi:10.1007/11427995-3
Barber MJ (2007) Modularity and community detection in bipartite network. Phys Rev E 76(6):066102. http://arxiv.org/abs/0707.1616
Bourqui R, Auber D (2009) Analysis of 4-connected components decomposition for graph visualization. Technical Report, LaBRI. http://www.labri.fr/
Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech P10008. http://arxiv.org/abs/0803.0476v2
Clauset A, Newman MEJ, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70:066111 (6 pp). doi:10.1103/PhysRevE.70.066111
Clauset A, Moore C, Newman MEJ (2008) Hierarchical structure and the prediction of missing links in networks. Nature 453:98–101
Donetti L, Munoz MA (2005) Improved spectral algorithm for the detection of network communities. Model Cooperative Behav Soc Sci 779:104–107
Du N, Wu B, Wang B, Wang Y (2008) Overlapping community detection in bipartite networks. In: Proceedings of the international conference on Web intelligence and intelligent agent technology, 2008. WI-IAT ’08, IEEE/WIC/ACM, vol 1, pp 176–179. http://arxiv.org/abs/0804.3636
Evans TS, Lambiotte R (2009) Line graphs, link partitions and overlapping communities. Phys Rev E 80:016105. http://arxiv.org/abs/0903.2181v2
Fortunato S (2010) Community detection in graphs. arXiv: 0906.0612v2 [physics.soc- ph]. Phys Rep 486(3–5):75–174. http://arxiv.org/abs/0906.0612
Fortunato S, Latora V, Marchior M (2004) Method to find community structures based on information centrality. Phys Rev E 70(5):056104
Girvan M, Newman MEJ (2002) Community structure in social and biological networks. In: Proceedings of the national academy of science (PNAS), USA, vol 99, pp 7821–7826
Gregory S (2008) A fast algorithm to find overlapping communities in networks. In: Proceedings of the 12th European conference on principles and practice of knowledge discovery in databases (PKDD 2008). ISBN 978-3-540-87478-2, pp 408–423
Gregory S (2009) Finding overlapping communities using disjoint community detection algorithms. In: Complex networks: results of the 1st international workshop on complex networks (CompleNet 2009), vol 207, Issue: 5, Publisher: Springer, Berlin, pp 47–61
Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12:103018. http://arxiv.org/abs/0910.5516v3
Guimera R, Sales-Pardo M, Amaral LAN (2007) Module identification in bipartite and directed networks. Phys Rev E 76(3):036102. doi:10.1103/PhysRevE.76.036102
Guimera R, Nunes Amaral LA (2005) Functional cartography of complex metabolic networks. Nature 433:895–900. http://arxiv.org/abs/q-bio/0502035
Handl J, Knowles J (2007) An evolutionary approach to multiobjective clustering. IEEE Trans Evol Comput 11(1):56–76
Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49(2):291–308
Kong X, Yu P (2011) gMLC: a multi-label feature selection framework for graph classification. Knowl Inf Syst (published online 8 mai 2011)
Lancichinetti A, Fortunato S, Kertesz J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015
Lipczak M, Milios E (2009) Agglomerative genetic algorithm for clustering in social networks genetic and evolutionary computation. In: Proceedings of the 11th annual conference on genetic and evolutionary computation, GECCO 2009 Montral Canada, pp 1243–1250
Liu X, Murata T (2009) Community detection in large-scale bipartite networks. In: Proceedings of the IEEE/WIC/ACM international joint conference on Web intelligence and intelligent agent technology, pp 50–57
Long B, Zhang Z, Yu P (2010) A general framework for relation graph clustering. Knowl Inf Syst 24:393–413
Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54:396–405
Mancoridis S, Mitchell BS, Rorres C, Chen Y, Gansner ER (1998) Using automatic clustering to produce high-level system organizations of source code. In: IEEE proceedings of the international on workshop on program understanding (IWPC’98), pp 45–53
Narasimhamurthy A, Greene D, Hurley N, Cunningham P (2010) Partitioning large networks without breaking communities. Knowl Inf Syst 25:345–369
Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113. http://arxiv.org/abs/cond-mat/0308217
Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74:036104. http://arxiv.org/abs/physics/0605087v3
Newman MEJ (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133
Pizzuti C (2008) Ga-net: a genetic algorithm for community detection in social networks. In: PPSN, volume 5199 of Lecture Notes in Computer Science, Springer, Berlin, pp 1081–1090
Pons P, Latapy M (2006) Computing communities in large networks using random walks. J Graph Algorithms Appl 10(2):191–218
Pothen A, Simon HD, Liou K-P (1990) Partitioning sparse matrices with eigenvectors of graphs. SIAM J Matrix Anal Appl 11(3):430–452
Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106. http://arxiv.org/abs/0709.2938
Tasgin M, Bingol H (2006) Community detection in complex networks using genetic. In: Procedings of the European conference on complex systems, (ECCS). http://arxiv.org/abs/0711.0491
Wakita K, Tsurumi T (2007) Finding community structure in a mega-scale social networking service. In: Proceedings of the international conference on WWW/Internet 2007 IADIS’2007, pp 153–162
Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442
Xiaofeng HZ, He X, Ding C, Simon H, Gu M (2001) Bipartite graph partitioning and data clustering. In: Proceedings of the tenth international conference on information and, knowledge management CIKM’0, pp 25–32
Xu X, Yuruk N, Feng Z, Schweiger TA (2007) SCAN: a structural clustering algorithm for networks. In: 13th international conference on knowledge discovery and data mining, KDD 2007, pp 824–833
Weihua Z, Zhongzhi Z, Jihong G, Shuigeng Z (2011) Evolutionary method for finding communities in bipartite networks. [Physics.data.an] http://arxiv.org/abs/1011.3315v3
Zhang S, Wang R, Zhang X (2007) Identification of overlapping community structure in complex networks using fuzzy C-means clustering. Physica A 374(1):483–490