We use cookies to improve your experience with our site.
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

  • 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.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return