We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Xin Liu, Tsuyoshi Murata. Detecting Communities in K-Partite K-Uniform (Hyper)Networks[J]. Journal of Computer Science and Technology, 2011, 26(5): 778-791. DOI: 10.1007/s11390-011-0177-0
Citation: Xin Liu, Tsuyoshi Murata. Detecting Communities in K-Partite K-Uniform (Hyper)Networks[J]. Journal of Computer Science and Technology, 2011, 26(5): 778-791. DOI: 10.1007/s11390-011-0177-0

Detecting Communities in K-Partite K-Uniform (Hyper)Networks

Funds: This work was supported in part by JSPS Grant-in-Aid under Grant No. 22300049 and IBM Ph.D. Fellowship.
More Information
  • Author Bio:

    Xin Liu is a Ph.D. candidate in the Department of Computer Science, Tokyo Institute of Technology. He received the B.S. degree in computing and information science from Wuhan University of Technology in 2004, and the M.S. degree in computer science from Wuhan University in 2007. His research interests includeWeb mining and social network analysis.

    Tsuyoshi Murata is an associate professor in the Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology. He obtained his doctor's degree in computer science at Tokyo Institute of Technology in 1997, on the topic of machine discovery of geometrical theorems. At Tokyo Institute of Technology, he conducts research on Web mining, artificial intelligence, and social network analysis. He is a member of IEEE, AAAI, ACM, JSAI, IPSJ and JSSST.

  • Received Date: September 30, 2010
  • Revised Date: July 03, 2011
  • Published Date: September 04, 2011
  • In social tagging systems such as Delicious and Flickr, users collaboratively manage tags to annotate resources. Naturally, a social tagging system can be modeled as a (user, tag, resource) hypernetwork, where there are three different types of nodes, namely users, resources and tags, and each hyperedge has three end nodes, connecting a user, a resource and a tag that the user employs to annotate the resource. Then how can we automatically cluster related users, resources and tags, respectively? This is a problem of community detection in a 3-partite, 3-uniform hypernetwork. More generally, given a K-partite K-uniform (hyper)network, where each (hyper)edge is a K-tuple composed of nodes of K different types, how can we automatically detect communities for nodes of different types? In this paper, by turning this problem into a problem of finding an efficient compression of the (hyper)network's structure, we propose a quality function for measuring the goodness of partitions of a K-partite K-uniform (hyper)network into communities, and develop a fast community detection method based on optimization. Our method overcomes the limitations of state of the art techniques and has several desired properties such as comprehensive, parameter-free, and scalable. We compare our method with existing methods in both synthetic and real-world datasets.
  • [1]
    Fortunato S. Community detection in graphs. Physics Reports, 2010, 486: 75-174.
    [2]
    Danon L, Duch L, Guilera A D, Arenas A. Comparing community structure identification. J. Stat. Mech, 2005, 9: P09008.
    [3]
    Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis. Phys. Rev. E, 2009, 80(5): 056117.
    [4]
    Leskovec J, Lang K J, Mahoney M W. Empirical comparison of algorithms for network community detection. In Proc. the 19th International Conference on World Wide Web, Raleigh, USA, Apr. 26-30, 2010, pp.631-640.
    [5]
    Shen H, Cheng X. Spectral methods for the detection of network community structure: A comparative analysis. J. Stat. Mech., 2010, 10: P10020.
    [6]
    Guimerà R, Pardo M S, Amaral L A N. Module identification in bipartite and directed networks. Phys. Rev. E, 2007, 76(3): 036102.
    [7]
    Zlati? V, Ghoshal G, Caldarelli G. Hypergraph topological quantities for tagged social networks. Phys. Rev. E, 2009, 80(3): 036118.
    [8]
    Neubauer N, Obermayer K. Towards community detection in k-partite k-uniform hypergraphs. In Workshop on Analyzing Networks and Learning with Graphs, Whistler, BC, Canada, Dec. 11, 2009.
    [9]
    Lu C, Chen X, Park E K. Exploit the tripartite network of social tagging for web clustering. In Proc. the 18th ACM Conference on Information and Knowledge Management, Hong Kong, China, Nov. 2-6, 2009, pp.1545-1548.
    [10]
    Zhou T, Ren J, Medo M, Zhang Y C. Bipartite network projection and personal recommendation. Phys. Rev. E, 2007, 76(4): 046115.
    [11]
    Barber M J. Modularity and community detection in bipartite network. Phys. Rev. E, 2007, 76(6): 066102.
    [12]
    Murata T, Ikeya T. A new modularity for detecting one-tomany correspondence of communities in bipartite networks. Advances in Complex Systems, 2010, 13(1): 19-31.
    [13]
    Suzuki K,Wakita K. Extracting multi-facet community structure from bipartite networks. In Proc. International Conference on Computational Science and Engineering, Vancouver, BC, Canada, Aug. 29-31, 2009, pp.312-319.
    [14]
    Murata T. Detecting communities from tripartite networks. In Proc. the 19th International Conference on World Wide Web, Raleigh, USA, Apr. 26-30, 2010, pp.1159-1160.
    [15]
    Murata T. Modularity for heterogeneous networks. In Proc. the 21st ACM Conference on Hypertext and Hypermedia, Toronto, Canada, Jun. 13-16, 2010, pp.129-134.
    [16]
    Lin Y R, Sun J, Castro P, Konuru R, Sundaram H, Kelliher A. Metafac: Community discovery via relational hypergraph factorization. In Proc. the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, Jun. 28-Jul. 1, 2009, pp.527-535.
    [17]
    Dhillon I S, Mallela S, Modha D S. Information-theoretic coclustering. In Proc. the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington DC, USA, Aug. 24-27, 2003, pp.89-98.
    [18]
    Li T. A general model for clustering binary data. In Proc. the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, USA, Aug. 21-24, 2005, pp.188-197.
    [19]
    Banerjee A, Dhillon I, Ghosh J, Merugu S, Modha D S. A generalized maximum entropy approach to Bregman co-clustering and matrix approximation. Journal of Machine Learning Research, 2007, 8: 1919-1986.
    [20]
    Long B, Zhang Z, Yu P S. A probabilistic framework for relational clustering. In Proc. the 13th ACM International Conference on Knowledge Discovery and Data Mining, San Jose, USA, Aug. 12-15, 2007, pp.470-479.
    [21]
    Newman M E J. Networks: An Introduction. New York: Oxford University Press, 2010.
    [22]
    Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks. Proc. Natl. Acad. Sci. USA, 2007, 104(18): 7327-7331.
    [23]
    Kernighan B, Lin S. An efficient heuristic procedure to partition graphs. Bell Syst. Tech. J., 1970, 49(2): 291-307.
    [24]
    Scott J. Social Network Analysis: A Handbook. Second Edition, Sage Publications, Newberry Park, CA, 2000.
    [25]
    Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 2004, 69(2): 026113.
    [26]
    Newman M E J. Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA, 2006, 103(23): 8577- 8582.
    [27]
    Fortunato S, Barthélemy M. Resolution limit in community detection. Proc. Natl. Acad. Sci. USA, 2007, 104(1): 36-41.
    [28]
    Shen H, Cheng X, Fang B. Covariance, correlation matrix, and the multiscale community structure of networks. Phys. Rev. E, 2010, 82(1): 016114.
    [29]
    Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69(6): 066133.
    [30]
    Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Phys. Rev. E, 2004, 70(6): 066111.
    [31]
    Duch L, Arenas A. Community detection in complex networks using extremal optimization. Phys. Rev. E, 2005, 72(2): 027104.
    [32]
    Medus A, Acuna G, Dorso C O. Detection of community structures in networks via global optimization. Physica A, 2005, 358(2-4): 593-604.
    [33]
    Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 2006, 74(3): 036104.
    [34]
    Schuetz P, Caflisch A. Efficient modularity optimization by multistep greedy algorithm and vertex refinement. Phys. Rev. E, 2008, 77(4): 046112.
    [35]
    Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. J. Stat. Mech., 2008, 10: P10008.
    [36]
    Zhang X S, Wang R S, Wang Y, Wang J, Qiu Y, Wang L, Chen L. Modularity optimization in community detection of complex networks. Europhys. Lett., 2009, 87(3): 38002.
    [37]
    Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A, 2010, 389(7): 1493-1500.
    [38]
    Gao B, Liu T Y, Zheng X, Cheng Q S, Ma W Y. Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering. In Proc. the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, USA, Aug. 21-24, 2005, pp.41-50.
    [39]
    Greco G, Guzzo A, Pontieri L. An information-theoretic framework for high-order co-clustering of heterogeneous objects. In Proc. the 15th Italian Symposium on Advanced Database Systems, Torre Canne, Italy, Jun. 17-20, 2007, pp.397-404.
    [40]
    Long B, Zhang Z F, Wu X Y, Yu P S. Spectral clustering for multi-type relational data. In Proc. the 23rd International Conference on Machine Learning, Pittsburgh, USA, Jun. 25- 29, 2006, pp.585-592.
    [41]
    Long B, Wu X, Zhang Z, Yu P S. Unsupervised learning on k-partite graphs. In Proc. the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, USA, Aug. 20-23, 2006, pp.317-326.
    [42]
    Singh A P, Gordon G J. Relational learning via collective matrix factorization. In Proc. the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.650—658, Las Vegas, USA, Aug. 24-27, 2008.
    [43]
    Singh A P, Gordon G J. A unified view of matrix factorization models. In Proc. the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Antwerp, Belgium, Sept. 15-19, 2008, pp.358-373.
    [44]
    Cattuto C, Schmitz C, Baldassarri A, Servedio V D P, Loreto V, Hotho A, Grahl M, Stumme G. Network properties of folksonomies. AI Communications, 2007, 20(4): 245-262.
    [45]
    Halpin H, Robu V, Shepherd H. The complex dynamics of collaborative tagging. In Proc. the 16th International Conference on World Wide Web, Banff, Canada, May 8-12, 2007, pp.211-220.
    [46]
    Long B, Wu X, Zhang Z, Yu P S. Community learning by graph approximation. In Proc. the 7th IEEE International Conference on Data Mining, Omaha, USA, Oct. 28-31, 2007, pp.232-241.
    [47]
    Long B, Zhang Z, Yu P S, Xu T. Clustering on complex graphs. In Proc. the 23rd National Conference on Artificial Intelligence, Chicago, USA, Jul. 13-17, 2008, pp.659-664.
    [48]
    Rissanen J. Modelling by shortest data description. Automatica, 1978, 14(5): 465-471.
    [49]
    Brandes U, Delling D, Gaertler M, GÄorke R, Hoefer M, Nikolski Z, Wagner D. On modularity—np-completeness and beyond. Technical Report 2006-19, ITI Wagner, Faculty of Informatics, UniversitÄat Karlsruhe, 2006.
    [50]
    Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E, 2007, 76(3): 036106.
    [51]
    Barber M J, Clark J W. Detecting network communities by propagating labels under constraints. Phys. Rev. E, 2009, 80(2): 026129.
    [52]
    Arenas A, Duch J, Fernández A, Gómez S. Size reduction of complex networks preserving modularity. New Journal of Physics, 2007, 9: 176.
    [53]
    Davis A, Gardner B B, Gardner M R. Deep South. Chicago: University of Chicago Press, IL, 1941.
    [54]
    Breiger R, Carley K, Pattison P (eds.) Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, Washington, DC: The National Academics Press, USA, 2003.
    [55]
    Jaccard P. Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull. Soc. Vaudoise Sci. Nat., 1901, 37: 547-579.
    [56]
    LÄu L, Zhou T. Link prediction in complex networks: A survey. Physica A, 2011, 390: 1150-1170.
  • Related Articles

    [1]Jun Hu, Bing Wang, Yu Liu, De-Yi Li. Personalized Tag Recommendation Using Social Influence[J]. Journal of Computer Science and Technology, 2012, 27(3): 527-540. DOI: 10.1007/s11390-012-1241-0
    [2]Loris Nanni, Alessandra Lumini. Cluster-Based Nearest-Neighbour Classifier and Its Application on the Lightning Classification[J]. Journal of Computer Science and Technology, 2008, 23(4): 573-581.
    [3]Haixun Wang, Jian Pei. Clustering by Pattern Similarity[J]. Journal of Computer Science and Technology, 2008, 23(4): 481-496.
    [4]Yu-Bao Liu, Jia-Rong Cai, Jian Yin, Ada Wai-Chee Fu. Clustering Text Data Streams[J]. Journal of Computer Science and Technology, 2008, 23(1): 112-128.
    [5]Juan J. Cuadrado Gallego, Daniel Rodri guez, Miguel Angel Sicilia, Miguel Garre Rubio, Angel Garci a Crespo. Software Project Effort Estimation Based on Multiple Parametric Models Generated Through Data Clustering[J]. Journal of Computer Science and Technology, 2007, 22(3): 371-378.
    [6]Bo Yang, Da-You Liu. A Heuristic Clustering Algorithm for Mining Communities in Signed Networks[J]. Journal of Computer Science and Technology, 2007, 22(2): 320-328.
    [7]QIAN WeiNing, GONG XueQing, ZHOU AoYing. Clustering in Very Large Databases Based on Distance and Density[J]. Journal of Computer Science and Technology, 2003, 18(1).
    [8]ZHOU Aoying, QIAN Weining, QIAN Hailei. Clustering DTDs: An Interactive Two-Level Approach[J]. Journal of Computer Science and Technology, 2002, 17(6).
    [9]HE Zengyou, XU Xiaofei, DENG Shengchun. Squeezer: An Efficient Algorithm for Clustering Categorical Data[J]. Journal of Computer Science and Technology, 2002, 17(5).
    [10]ZHUANG Yueting, RUI Yong, Thomas S.Huang. Video Key Frame Extraction by Unsupervised Clustering and Feedback Adjustment[J]. Journal of Computer Science and Technology, 1999, 14(3): 283-287.

Catalog

    Article views (25) PDF downloads (1842) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return