Wangqun Lin
Philip S. Yu
ABSTRACT
With the recent advances in information networks, the problem of community detection has attracted much attention in the last decade. While network community detection has been ubiquitous, the task of collecting complete network data remains challenging in many real-world applications. Usually the collected network is incomplete with most of the edges missing. Commonly, in such networks, all nodes with attributes are available while only the edges within a few local regions of the network can be observed. In this paper, we study the problem of detecting communities in incomplete information networks with missing edges. We first learn a distance metric to reproduce the link-based distance between nodes from the observed edges in the local information regions. We then use the learned distance metric to estimate the distance between any pair of nodes in the network. A hierarchical clustering approach is proposed to detect communities within the incomplete information networks. Empirical studies on real-world information networks demonstrate that our proposed method can effectively detect community structures within incomplete information networks.
- G. Agarwal and D. Kempe. Modularity-maximizing graph communities via mathematical programming. European Physical Journal B, 66:409--418, 2008.Google Scholar
Cross Ref
- C. Aggarwal, Y. Xie, and P. Yu. Towards community detection in locally heterogeneous networks. SDM, pages 391--402, 2011.Google ScholarCross Ref
- Y. Ahn, J. Bagrow, and S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466:761--764, 2010.Google ScholarCross Ref
- H. Alani, S. Dasmahapatra, K. O'Hara, and N. Shadbolt. Identifying communities of practice through ontology network analysis. Intelligent Systems, 18(2):18--25, 2003. Google ScholarDigital Library
- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Google ScholarCross Ref
- T. Evans and R. Lambiotte. Line graphs, link partitions and overlapping communities. Physical Review E, 80:016105, 2009.Google ScholarCross Ref
- Z. Feng, X. Xu, N. Yuruk, and T. A. J. Schweiger. A novel similarity-based modularity function for graph partitioning. In DaWak, pages 385--396, 2007. Google ScholarDigital Library
- S. Fortunato and M. Barthelemy. Resolution limit in community detection. Proceedings of The National Academy of Sciences, 104(1):36--41, 2007.Google ScholarCross Ref
- R. Ge, M. Ester, B. J. Gao, Z. Hu, B. K. Bhattacharya, and B. Ben-moshe. Joint cluster analysis of attribute data and relationship data: The connected k-center problem, algorithms and applications. ACM Transactions on Knowledge Discovery From Data, 2:1--35, 2008. Google ScholarDigital Library
- B. H. Good, Y. A. de Montjoye, and A. Clauset. The performance of modularity maximization in practical contexts. Physical Review E, 81:046106, 2010.Google ScholarCross Ref
- R. Guimera and L. N. Amaral. Functional cartography of complex metabolic networks. Nature, 433(7028):895--900, 2005.Google ScholarCross Ref
- J. H. H. D. Y. S. Y. L. J. Huang, H. Sun. SHRINK: a structural clustering algorithm for detecting hierarchical communities in networks. In CIKM, pages 219--228, 2010. Google ScholarDigital Library
- M. Kim and J. Leskovec. The network completion problem: Inferring missing nodes and edges in networks. In SDM, pages 47--58, 2011.Google ScholarCross Ref
- J. Z. Z. N. L. Tang, H. Liu. Community evolution in dynamic multi-mode networks. KDD, pages 677--685, 2008. Google ScholarDigital Library
- A. Lancichinetti and S. Fortunato. Community detection algorithms: A comparative analysis. Physical Review E, 80(5):056117, 2009.Google ScholarCross Ref
- J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney. Statistical properties of community structure in large social and information networks. WWW, pages 695--704, 2008. Google ScholarDigital Library
- J. Leskovec, K. Lang, and M. Mahoney. Empirical comparison of algorithms for network community detection. WWW, pages 631--640, 2010. Google ScholarDigital Library
- Y. Lin, J. Sun, P. Castro, R. Konuru, H. Sundaram, and A. Kelliher. Metafac: community discovery via relational hypergraph factorization. KDD, pages 527--536, 2009. Google ScholarDigital Library
- M. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.Google ScholarCross Ref
- G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435:814, 2005.Google ScholarCross Ref
- M. Rosvall and C. Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105:1118, 2008.Google ScholarCross Ref
- M. Sales-Pardo, R. Guimerà, A. Moreira, and L. Amaral. Extracting the hierarchical organization of complex systems. Proceedings of the National Academy of Sciences, 104(39):15224--15229, 2007.Google ScholarCross Ref
- P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93--106, 2008.Google ScholarDigital Library
- J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000. Google ScholarDigital Library
- M. Shiga, I. Takigawa, and H. Mamitsuka. A spectral clustering approach to optimally combining numerical vectors with a modular network. KDD, pages 647--656, 2007. Google ScholarDigital Library
- Y. Tian, R. Hankins, and J. Patel. Efficient aggregation for graph summarization. In SIGMOD, pages 567--580, 2008. Google ScholarDigital Library
- C. Tsai and C. Chiu. Developing a feature weight self-adjustment mechanism for a k-means clustering algorithm. Computational Statistics Data Analysis, 52:4658--4672, 2008. Google ScholarDigital Library
- K. Wakita and T. Tsurumi. Finding community structure in mega-scale social networks. In WWW, pages 1275--1276, 2007. Google ScholarDigital Library
- E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In NIPS, pages 505--512, 2002.Google ScholarDigital Library
- X. Xu, N. Yuruk, Z. Feng, and T. A. J. Schweiger. Scan: A structural clustering algorithm for networks. In KDD, pages 824--833, 2007. Google ScholarDigital Library
- Y. Zhou, H. Cheng, and J. Yu. Graph clustering based on structural/attribute similarities. VLDB Endowment, 2:718--729, 2009. Google ScholarDigital Library
Index Terms
- Community detection in incomplete information networks
Recommendations
An optimisation tool for robust community detection algorithms using content and topology information
AbstractWith the recent prevalence of information networks, the topic of community detection has gained much interest among researchers. In real-world networks, node attribute (content information) is also available in addition to topology information. ...
Edge Weight Method for Community Detection in Scale-Free Networks
WIMS '14: Proceedings of the 4th International Conference on Web Intelligence, Mining and Semantics (WIMS14)In this paper, we proposed edge-weight based method to perform a community detection in scale-free networks. Our main idea is that communities are formed from edges. We believe that in scale-free networks, each edge is not equal. Edges that connect to ...
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. ...
Comments