Identifying overlapping communities in folksonomies or tripartite hypergraphs

Folksonomies like Delicious and LastFm are modelled as tri-partite (user-resource-tag) hypergraphs for studying their network properties. Detecting communities of similar nodes from such networks is a challenging problem. Most exist-ing algorithms for community detection in folksonomies as-sign unique communities to nodes, whereas in reality, users have multiple topical interests and the same resource is often tagged with semantically different tags. The few attempts to detect overlapping communities work on projections of the hypergraph, which results in significant loss of informa-tion contained in the original tripartite structure. We pro-pose the first algorithm to detect overlapping communities in folksonomies using the complete hypergraph structure. Our algorithm converts a hypergraph into its corresponding line-graph, using measures of hyperedge similarity, whereby any community detection algorithm on unipartite graphs can be used to produce overlapping communities in the folksonomy. Through extensive experiments on synthetic as well as real folksonomy data, we demonstrate that the proposed algo-rithm can detect better community structures as compared to existing state-of-the-art algorithms for folksonomies