Home // IMMM 2013, The Third International Conference on Advances in Information Mining and Management // View article

Truss Decomposition for Extracting Communities in Bipartite Graph

Authors:
Yanting Li
Tetsuji Kuboyama
Hiroshi Sakamoto

Keywords: bipartite graph, triangle, truss decomposition, dense subgraph, community discovery

Abstract:
We propose a novel method for extracting communities, i.e., dense subgraphs, embedded into a bipartite graph. Our method is based on a technique for graph decomposition. Decomposing a large graph into cohesive subgraphs plays an important role in identifying community structures in social network analysis. Among a lot of definitions of cohesive subgraphs, the k-truss formed by triangles is one of the simplest cohesive subgraphs with a good trade-off between computational efficiency and clique approximation. This decomposition is, however, not applicable to bipartite graphs because bipartite graphs contain no triangles. In this paper, a quasi-truss decomposition algorithm for bipartite graphs is proposed based on the truss decomposition algorithm for general graphs. The proposed method can be used for analyzing the international business, such as the relationship between clients and sales volume in a certain period, and also analyze the social networking, such as users-topics relations in the twitter community.

Pages: 76 to 80

Copyright: Copyright (c) IARIA, 2013

Publication date: November 17, 2013

Published in: conference

ISSN: 2326-9332

ISBN: 978-1-61208-311-7

Location: Lisbon, Portugal

Dates: from November 17, 2013 to November 21, 2013