Community Detection in Multi-Partite Multi-Relational Networks Based on Information Compression
Abstract
Community detection in uni-partite single-relational networks which contain only one type of nodes and edges has been extensively studied in the past decade. However, many real-world systems are naturally described as multi-partite multi-relational networks which contain multiple types of nodes and edges. In this paper, we propose an information compression based method for detecting communities in such networks. Specifically, based on the minimum description length (MDL) principle, we propose a quality function for evaluating partitions of a multi-partite multi-relational network into communities, and develop a heuristic algorithm for optimizing the quality function. We demonstrate that our method outperforms the state-of-the-art techniques in both synthetic and real-world networks.
References
[1]
Girvan, M. and Newman, M. E. J., “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. USA, 99, pp. 7821–7826, 2002.
[2]
Flake G. W., Lawrence S., Giles C. L., Coetzee F. M.: “Self-organization and identification of web communities,”. IEEE Computer 35(3), pp. 66–70 (2002)
[3]
Dourisboure, Y., Geraci, F. and Pellegrini, M., “Extraction and classification of dense communities in the web,” in Proc. of the 16th International Conference on World Wide Web (Banff, Alberta, Canada), pp. 461–470, May 2007.
[4]
Guimerà R., Amaral L. A. N.: “Functional cartography of complex metabolic networks,”. Nature 433, 895–900 (2005)
[5]
Palla G., Derényi I., Farkas I., Vicsek T.: “Uncovering the overlapping community structure of complex networks in nature and society,”. Nature, 435(7043), 814–818 (2005)
[6]
Fortunato S.: “Community detection in graphs,”. Physics Reports 486, 75–174 (2010)
[7]
Gulbahce N., Lehmann S.: “The art of community detection,”. BioEssays 30(10), 934–938 (2008)
[8]
NewmanM. E. J.: Networks: An Introduction. Oxford University Press, New York (2010)
[9]
Lancichinetti, A., Radicchi, F., Ramasco, J. J. and Fortunato, S., “Finding statistically significant communities in networks,” PloS one, 6, 4, e18961, 2011.
[10]
Sun, Y., Yu, Y. and Han, J., “Ranking-based clustering of heterogeneous information networks with star network schema,” in Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Paris, France), pp. 797–806, Aug 2009.
[11]
Comar P. M., Tan P. N., Jain A. K.: “A framework for joint community detection across multiple related networks,”. Neurocomputing, 76(1), 93–104 (2012)
[12]
Lin, Y. R., Sun, J., Castro, P., Konuru, R., Sundaram, H. and Kelliher, A., “Metafac: community discovery via relational hypergraph factorization,” in Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Paris, France), pp. 527–535, Aug 2009.
[13]
Liu X., Liu W., Murata T., Wakita K.: “A framework for community detection in heterogeneous multi-relational networks,”. Advances in Complex Systems, 17(1450018), 1–21 (2014)
[14]
Rissanen J.: “Modelling by shortest data description,”. Automatica 14(5), 465–471 (1978)
[15]
Newman M. E. J.: “Communities, modules and large-scale structure in networks,”. Nature Physics, 8(1), 25–31 (2012)
[16]
Danon, L., Duch, J., D.-Guilera, A. and Arenas, A. “Comparing community structure identification,” J. Stat. Mech., P09008, 2005.
[17]
Lancichinetti, A. and Fortunato, S., “Community detection algorithms: a comparative analysis,” Phys. Rev. E, 80, 056117, 2009.
[18]
Orman, G. K., Labatut, V. and Cherifi, H., “Comparative evaluation of community detection algorithms: a topological approach,” J. Stat. Mech., P08001, 2012.
[19]
Newman, M. E. J., “Fast algorithm for detecting community structure in networks,” Phys. Rev. E, 69, 066133, 2004.
[20]
Clauset, A., Newman, M. E. J. and Moore, C., “Finding community structure in very large networks,” Phys. Rev. E, 7, 066111, 2004.
[21]
Blondel, V. D., Guillaume, J. L., Lambiotte, R. and Lefebvre, E., “Fast unfolding of communities in large networks,” J. Stat. Mech., P10008, 2008.
[22]
Liu X., Murata T.: “Advanced modularity-specialized label propagation algorithm for detecting communities in networks,”. Physica A, 389(7), 1493–1500 (2010)
[23]
Newman, M. E. J., “Finding community structure in networks using the eigenvectors of matrices,” Phys. Rev. E, 74, 036104, 2006.
[24]
Shen, H. and Cheng, X., “Spectral methods for the detection of network community structure: a comparative analysis,” J. Stat. Mech., P10020, 2010.
[25]
Ball, B. Karrer, B. and Newman, M. E. J., “Efficient and principled method for detecting communities in networks,” Phys. Rev. E, 84, 036103, 2011.
[26]
Karrer, B. and Newman, M. E. J., “Stochastic blockmodels and community structure in networks,” Phys. Rev. E, 83, 016107, 2011.
[27]
Mucha P. J., Richardson T., Macon K., Porter M. A., Onnela J. P.: “Community structure in time-dependent, multiscale, and multiplex networks,”. Science 328, 876–878 (2010)
[28]
Tang L., Liu H., Zhang J.: “Identifying evolving groups in dynamic multimode networks,”. IEEE Transactions on Knowledge and Data Engineering 24(1), 72–85 (2012)
[29]
Tang L., Wang X., Liu H.: “Community detection via heterogeneous interaction analysis,”. Data Mining and Knowledge Discovery 25(1), 1–33 (2012)
[30]
Popescul, A., Flake, G.W., Lawrence, S., Ungar, L. H. and Giles, C. L., “Clustering and identifying temporal trends in document databases,” in Proc. of the IEEE Advances in Digital Libraries (Bethesda, MD, USA), pp. 173–182, May 2000.
[31]
Dhillon, I. S., Mallela, S. and Modha, D. S., “Information-theoretic co-clustering,” in Proc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Washington, DC, USA), pp. 89–98, Aug 2003.
[32]
Rosvall M., Bergstrom C. T.: “An information-theoretic framework for resolving community structure in complex networks,”. Proc. Natl. Acad. Sci. USA 104(18), 7327–7331 (2007)
[33]
Sun, J., Faloutsos, C., Papadimitriou, S. and Yu, P. S., “Graphscope: parameterfree mining of large time-evolving graphs,” in Proc. of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (San Jose, CA, USA), pp. 687–696, Aug 2007.
[34]
Liu X., Murata T.: “Detecting communities in k-partite k-uniform (hyper) networks,”. Journal of Computer Science and Technology, 26(5), 778–791 (2011)
[35]
Long, B., Wu, X., Zhang, Z. and Yu, P. S., “Community learning by graph approximation,” in Proc. of the 7th IEEE International Conference on Data Mining, (Cambridge, MA, USA), pp. 232–241, Oct. 2007.
[36]
Long, B., Zhang, Z., Yu, P. S. and Xu, T., “Clustering on complex graphs,” in Proc. of the 23rd National Conference on Artificial Intelligence (Chicago, IL, USA), pp. 659–664, 2008. 37. Rissanen, J. “A universal prior for integers and estimation by minimum description length,”. The Annals of Statistics 11, 2, 416–43 1983.
[37]
Rissanen J.: “A universal prior for integers and estimation by minimum description length,” The Annals of Statistics, 11(2), 416–431 1983
[38]
Waltman, L. and van Eck, N. J., “A smart local moving algorithm for largescale modularity-based community detection,” The European Physical Journal B, 86, 11, 471, 2013.
[39]
Rotta, R. and Noack, A., “Multilevel local search algorithms for modularity clustering,” ACM Journal of Experimental Algorithmics, 16, 2, 2.3, 2011.
[40]
Schuetz, P. and Caflisch, A., “Efficient modularity optimization by multistep greedy algorithm and vertex refinement,” Phys. Rev. E, 77, 046112, 2008.
[41]
Arenas, A., Duch, J., Fernández, A. and Gómez, S., “Size reduction of complex networks preserving modularity,” New Journal of Physics, 9 176, 2007.
[42]
Lancichinetti, A., Fortunato, S. and Radicchi, F., “Benchmark graphs for testing community detection algorithms,” Phys. Rev. E, 78, 046110, 2008.
[43]
Lancichinetti, A. and Fortunato, S., “Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities,” Phys. Rev. E, 80, 016118, 2009.
[44]
Fred, A. L. N. and Jain, A. K., “Robust data clustering,” in Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Madison, WI, USA), pp. 128–133, Jun 2003.
[45]
Ruan, Y., Fuhry, D. and Parthasarathy, S., “Efficient community detection in large networks using content and links,” in Proc. of the 22nd International Conference on World Wide Web (Rio de Janeiro, Brazil), pp. 1089–1098, May 2013.
[46]
Günnemann, S., Boden, B. and Seidl, T., “Db-csc: a density-based approach for subspace clustering in graphs with feature vectors,” in Proc. of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (Athens, Greece), pp. 565–580, Sep 2011.
[47]
Günnemann S., Färber I., Boden B., Seidl T.: “Gamer: a synthesis of subspace clustering and dense subgraph mining,”. Knowledge and information systems, 40(2), 243–278 (2013)
[48]
Günnemann, S., Boden, B., Färber, I. and Seidl, T., “Efficient mining of combined subspace and subgraph clusters in graphs with feature vectors,” in Proc. of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining (Gold Coast, Australia), pp. 261–275, Apr 2013.
[49]
Boden, B., Ester, M. and Seidl, T., “Density-based subspace clustering in heterogeneous networks,” in Proc. of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (Nancy, France), pp. 149–164, Sep 2014.
[50]
Yang, J., McAuley, J. and Leskovec, J., “Community detection in networks with node attributes,” in Proc. of the 13th IEEE International Conference on Data Mining, (Dallas, TX, USA), pp. 1151–1156, Dec 2013.
[51]
Barber, M. J., “Modularity and community detection in bipartite networks,” Phys. Rev. E, 76, 066102, 2007.
Index Terms
- Community Detection in Multi-Partite Multi-Relational Networks Based on Information Compression
Index terms have been assigned to the content through auto-classification.
Recommendations
Community detection for emerging social networks
Many famous online social networks, e.g., Facebook and Twitter, have achieved great success in the last several years. Users in these online social networks can establish various connections via both social links and shared attribute information. ...
Community-based anomaly detection in evolutionary networks
Networks of dynamic systems, including social networks, the World Wide Web, climate networks, and biological networks, can be highly clustered. Detecting clusters, or communities, in such dynamic networks is an emerging area of research; however, less ...
Community structure detection from networks with weighted modularity
Highlights- Propose an algorithm to overcome the resolution limitation of traditional approaches.
AbstractCommunity detection from networks is an emerging topic in modern network science. Communities are defined as clusters of nodes or vertices that share higher concentration of edges among themselves than sharing with other nodes in the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2016 Ohmsha and Springer Japan.
Publisher
Ohmsha
Japan
Publication History
Published: 01 March 2016
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in