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

• 作 者: Xin Liu Tsuyoshi Murata
• 机 构: Department of Computer Science, Tokyo Institute of Technology, Tokyo 152-8552, Japan
• 出 处: 计算机科学技术学报（英文版）
• 发表日期: 2011年5期
• 关键词: community detection bipartite graph tripartite hypergraph clustering social tagg
• 基金项目: JSPS Grant-in-Aid under

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) hypetwork,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 hypetwork.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 ting 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.