Detecting Communities in Tripartite Hypergraphs
arXiv:1011.1043 · doi:10.1007/s11390-011-0177-0
Abstract
In social tagging systems, also known as folksonomies, users collaboratively manage tags to annotate resources. Naturally, social tagging systems can be modeled as a tripartite hypergraph, 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 detect user, resource and tag communities from the tripartite hypergraph? In this paper, by turning the problem into a problem of finding an efficient compression of the hypergraph's structure, we propose a quality function for measuring the goodness of partitions of a tripartite hypergraph into communities. Later, we develop a fast community detection algorithm based on minimizing the quality function. We explain advantages of our method and validate it by comparing with various state of the art techniques in a set of synthetic datasets.
arXiv comment4 pages, 3 figures
References in corpus (24)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Comparing community structure identification
- Link Prediction in Complex Networks: A Survey
- Community detection algorithms: a comparative analysis
- Community detection in complex networks using Extremal Optimization
- How to project a bipartite network?
- An information-theoretic framework for resolving community structure in complex networks
- Modularity and community detection in bipartite networks
- Module identification in bipartite and directed networks
- Detecting network communities by propagating labels under constraints
- Size reduction of complex networks preserving modularity
- Advanced modularity-specialized label propagation algorithm for detecting communities in networks
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Spectral methods for the detection of network community structure: a comparative analysis
- Hypergraph topological quantities for tagged social networks
- Covariance, correlation matrix and the multi-scale community structure of networks