An Extension of Community Extraction Algorithm on Bipartite Graph

HIROSHI, SAKAMOTO and KOJI, MAEDA and TETSUJI, KUBOYAMA and YANTING, LI (2014) An Extension of Community Extraction Algorithm on Bipartite Graph. In: International Conference on Advances in Computer and Electronics Technology - ACET 2014, 26 - 27 August, 2014, City University of Hongkong, Hongkong.

20140911_050411.pdf - Published Version

Download (761kB) | Preview
Official URL:


We introduce a truss decomposition algorithm for bipartite graphs. A subgraph G of a graph is called k-truss if there are at least k-2 triangles containing any edge e of G. By a standard breadth-first-search algorithm, we can compute the truss decomposition for large graphs. To extract a dense substructure that represents community in graph G, this method avoids the intractable problem of clique detection. The truss decomposition is not, however, applicable to the bipartite graphs due to its definition. For this problem, we have proposed quasi-truss decomposition introducing an additional set of edges. For this decomposition, there is another problem such that dense subgraphs G1 and G2 are connected with a small number of edges. The previous algorithm detects the sparse structure H = G1 ⋃ G2 as quasi-truss due to the definition. In this paper, we improve the algorithm to extract denser substructures by removing such sparse edges with a top-down strategy. The extended algorithm has been implemented, and compared its performance with the previous algorithm for bipartite graphs obtained from real data.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: —k-truss, community extraction, bipartite graph.
Depositing User: Mr. John Steve
Date Deposited: 28 May 2019 09:27
Last Modified: 28 May 2019 09:27

Actions (login required)

View Item View Item