TY - GEN
T1 - Truss-based Community Search over Large Directed Graphs
AU - Liu, Qing
AU - Zhao, Minjun
AU - Huang, Xin
AU - Xu, Jianliang
AU - Gao, Yunjun
N1 - Funding Information:
This paper studies truss-based community search over large directed graphs. First, we devise a new community model called D-truss for community search over directed graphs. With the D-truss model, we formally define the problem of D-truss community search over directed graphs. Given a directed graph G and a query vertex set Q, the problem is to find the D-truss containing Q with the minimum diameter. As this problem is NP-hard, we propose two efficient polynomial algorithms with 2-approximation guarantee. An indexing method based on the D-truss decomposition results is further developed to expedite the algorithms. Extensive experimental results on large real-world networks with ground-truth communities confirm the effectiveness and efficiency of our proposed model and algorithms. Acknowledgments. This work is supported by Research Grants Council of Hong Kong under GRF Projects 12200819, 12200917, CRF Project C6030-18GF, the NSFC under Grant No. 61702435 & 61972338, the National Key R&D Program of China under Grant No. 2018YFB1004003, the NSFC-Zhejiang Joint Fund under Grant No. U1609217, and the ZJU-Hikvision Joint Project.
PY - 2020/6/14
Y1 - 2020/6/14
N2 - Community search enables personalized community discovery and has wide applications in large real-world graphs. While community search has been extensively studied for undirected graphs, the problem for directed graphs has received attention only recently. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time. To address the limitations, in this paper, we systematically study the problem of community search over large directed graphs. We start by presenting a novel community model, called D-truss, based on two distinct types of directed triangles, i.e., flow triangle and cycle triangle. The D-truss model brings nice structural and computational properties and has many advantages in comparison with the existing models. With this new model, we then formulate the D-truss community search problem, which is proved to be NP-hard. In view of its hardness, we propose two efficient 2-approximation algorithms, named Global and Local, that run in polynomial time yet with quality guarantee. To further improve the efficiency of the algorithms, we devise an indexing method based on D-truss decomposition. Consequently, the D-truss community search can be solved upon the D-truss index without time-consuming accesses to the original graph. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.
AB - Community search enables personalized community discovery and has wide applications in large real-world graphs. While community search has been extensively studied for undirected graphs, the problem for directed graphs has received attention only recently. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time. To address the limitations, in this paper, we systematically study the problem of community search over large directed graphs. We start by presenting a novel community model, called D-truss, based on two distinct types of directed triangles, i.e., flow triangle and cycle triangle. The D-truss model brings nice structural and computational properties and has many advantages in comparison with the existing models. With this new model, we then formulate the D-truss community search problem, which is proved to be NP-hard. In view of its hardness, we propose two efficient 2-approximation algorithms, named Global and Local, that run in polynomial time yet with quality guarantee. To further improve the efficiency of the algorithms, we devise an indexing method based on D-truss decomposition. Consequently, the D-truss community search can be solved upon the D-truss index without time-consuming accesses to the original graph. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.
KW - community search
KW - d-truss
KW - directed graph
UR - http://www.scopus.com/inward/record.url?scp=85085856331&partnerID=8YFLogxK
U2 - 10.1145/3318464.3380587
DO - 10.1145/3318464.3380587
M3 - Conference contribution
AN - SCOPUS:85085856331
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 2183
EP - 2197
BT - SIGMOD 2020 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
PB - Association for Computing Machinery (ACM)
T2 - 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD 2020
Y2 - 14 June 2020 through 19 June 2020
ER -