Abstract
We consider the community search problem defined upon a large graph G: given a query vertex q in G, to find as output all the densely connected subgraphs of G, each of which contains the query v. As an online, query-dependent variant of the well-known community detection problem, community search enables personalized community discovery that has found widely varying applications in real-world, large-scale graphs. In this paper, we study the community search problem in the truss-based model aimed at discovering all dense and cohesive k-truss communities to which the query vertex q belongs. We introduce a novel equivalence relation, k-truss equivalence, to model the intrinsic density and cohesiveness of edges in k-truss communities. Consequently, all the edges of G can be partitioned to a series of k-truss equivalence classes that constitute a space-efficient, truss-preserving index structure, EquiTruss. Community search can be henceforth addressed directly upon EquiTruss without repeated, time-demanding accesses to the original graph, G, which proves to be theoretically optimal. In addition, EquiTruss can be efficiently updated in a dynamic fashion when G evolves with edge insertion and deletion. Experimental studies in real-world, large-scale graphs validate the efficiency and effectiveness of EquiTruss, which has achieved at least an order of magnitude speedup in community search over the state-of-the-art method, TCP-Index.
- N. Barbieri, F. Bonchi, E. Galimberti, and F. Gullo. Efficient and Effective Community Search. Data Min. Knowl. Discov., 29(5):1406--1433, 2015. Google ScholarDigital Library
- A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order Organization of Complex Networks. Science, 353(6295):163--166, 2016.Google Scholar
- F. Bonchi, F. Gullo, A. Kaltenbrunner, and Y. Volkovich. Core Decomposition of Uncertain Graphs. In KDD'14, pages 1316--1325, 2014. Google ScholarDigital Library
- T. Chakraborty, S. Patranabis, P. Goyal, and A. Mukherjee. On the Formation of Circles in Co-authorship Networks. In KDD'15, pages 109--118, 2015. Google ScholarDigital Library
- J. Cohen. Trusses: Cohesive Subgraphs for Social Network Analysis. NSA:Technical report, 2008.Google Scholar
- W. Cui, Y. Xiao, H. Wang, Y. Lu, and W. Wang. Online Search of Overlapping Communities. In SIGMOD'13, pages 277--288, 2013. Google ScholarDigital Library
- W. Cui, Y. Xiao, H. Wang, and W. Wang. Local Search of Communities in Large Graphs. In SIGMOD'14, pages 991--1002, 2014. Google ScholarDigital Library
- Y. Fang, R. Cheng, X. Li, S. Luo, and J. Hu. Effective Community Search over Large Spatial Graphs. Proc. VLDB Endow., 10(6):709--720, 2017. Google ScholarDigital Library
- Y. Fang, R. Cheng, S. Luo, and J. Hu. Effective Community Search for Large Attributed Graphs. Proc. VLDB Endow., 9(12):1233--1244, 2016. Google ScholarDigital Library
- F. Harary and D. R. White. The Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density. Sociological Methodology, 31(1):305--359, 2001.Google ScholarCross Ref
- X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. Querying K-truss Community in Large and Dynamic Graphs. In SIGMOD'14, pages 1311--1322, 2014. Google ScholarDigital Library
- X. Huang and L. V. S. Lakshmanan. Attribute truss community search. Proc. VLDB Endow., 10(9):949 -- 960, 2017. Google ScholarDigital Library
- X. Huang, L. V. S. Lakshmanan, J. X. Yu, and H. Cheng. Approximate Closest Community Search in Networks. Proc. VLDB Endow., 9(4):276--287, 2015. Google ScholarDigital Library
- X. Huang, W. Lu, and L. V. Lakshmanan. Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms. In SIGMOD'16, pages 77--90, 2016. Google ScholarDigital Library
- W. Khaouid, M. Barsky, V. Srinivasan, and A. Thomo. K-core Decomposition of Large Networks on a Single PC. Proc. VLDB Endow., 9(1):13--23, 2015. Google ScholarDigital Library
- J. Kim, W.-S. Han, S. Lee, K. Park, and H. Yu. OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs. In SIGMOD'14, pages 637--648, 2014. Google ScholarDigital Library
- D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos. Summarizing and Understanding Large Graphs. Stat. Anal. Data Min., 8(3):183--202, 2015. Google ScholarDigital Library
- M. Latapy. Main-memory Triangle Computations for Very Large (Sparse (Power-law)) Graphs. Theor. Comput. Sci., 407(1--3):458--473, 2008. Google ScholarDigital Library
- K. LeFevre and E. Terzi. GraSS: Graph Structure Summarization. In SDM, 2010.Google ScholarCross Ref
- J. Leskovec, K. J. Lang, and M. Mahoney. Empirical Comparison of Algorithms for Network Community Detection. In WWW'10, pages 631--640, 2010. Google ScholarDigital Library
- R.-H. Li, L. Qin, J. X. Yu, and R. Mao. Influential Community Search in Large Networks. Proc. VLDB Endow., 8(5):509--520, 2015. Google ScholarDigital Library
- S. Navlakha, R. Rastogi, and N. Shrivastava. Graph Summarization with Bounded Error. In SIGMOD'08, pages 419--432, 2008. Google ScholarDigital Library
- M. Ortmann and U. Brandes. Triangle Listing Algorithms: Back from the Diversion. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, pages 1--8, 2014. Google ScholarDigital Library
- M. Riondato, D. García-Soriano, and F. Bonchi. Graph Summarization with Quality Guarantees. Data Min. Knowl. Discov., 31(2):314--349, 2017. Google ScholarDigital Library
- A. E. Sariyuce, B. Gedik, G. Jacques-Silva, K.-L. Wu, and U. V. Catalyurek. Incremental K-core Decomposition: Algorithms and Evaluation. The VLDB Journal, 25(3):425--447, 2016. Google ScholarDigital Library
- A. E. Sariyüce and A. Pinar. Fast Hierarchy Construction for Dense Subgraphs. Proc. VLDB Endow., 10(3):97--108, 2016. Google ScholarDigital Library
- A. E. Sariyuce, C. Seshadhri, A. Pinar, and U. V. Catalyurek. Finding the Hierarchy of Dense Subgraphs Using Nucleus Decompositions. In WWW'15, pages 927--937, 2015. Google ScholarDigital Library
- Y. Shao, L. Chen, and B. Cui. Efficient Cohesive Subgraphs Detection in Parallel. In SIGMOD'14, pages 613--624, 2014. Google ScholarDigital Library
- M. Sozio and A. Gionis. The Community-search Problem and How to Plan a Successful Cocktail Party. In KDD'10, pages 939--948, 2010. Google ScholarDigital Library
- Y. Tian, R. A. Hankins, and J. M. Patel. Efficient aggregation for graph summarization. In SIGMOD'08, pages 567--580, 2008. Google ScholarDigital Library
- C. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. Tsiarli. Denser Than the Densest Subgraph: Extracting Optimal Quasi-cliques with Quality Guarantees. In KDD'13, pages 104--112, 2013. Google ScholarDigital Library
- J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural Diversity in Social Contagion. Proceedings of the National Academy of Sciences, 109(16):5962--5966, 2012.Google ScholarCross Ref
- J. Wang and J. Cheng. Truss Decomposition in Massive Networks. Proc. VLDB Endow., 5(9):812--823, 2012. Google ScholarDigital Library
- Y. Wu, R. Jin, J. Li, and X. Zhang. Robust Local Community Detection: On Free Rider Effect and Its Elimination. Proc. VLDB Endow., 8(7):798--809, 2015. Google ScholarDigital Library
- J. Xie, S. Kelley, and B. K. Szymanski. Overlapping Community Detection in Networks: The State-of-the-art and Comparative Study. ACM Comput. Surv., 45(4):43:1--43:35, 2013. Google ScholarDigital Library
- J. Zhang, P. S. Yu, and Y. Lv. Enterprise Employee Training via Project Team Formation. In WSDM'17, pages 3--12, 2017. Google ScholarDigital Library
- F. Zhao and A. K. H. Tung. Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis. Proc. VLDB Endow., 6(2):85--96, 2012. Google ScholarDigital Library
Index Terms
- Truss-based community search: a truss-equivalence based indexing approach
Recommendations
Truss-based Community Search over Large Directed Graphs
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of DataCommunity 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 ...
Querying k-truss community in large and dynamic graphs
SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of DataCommunity detection which discovers densely connected structures in a network has been studied a lot. In this paper, we study online community search which is practically useful but less studied in the literature. Given a query vertex in a graph, the ...
I/O efficient k-truss community search in massive graphs
AbstractCommunity detection that discovers all densely connected communities in a network has been studied a lot. In this paper, we study online communitysearch for query-dependent communities, which is a different but practically useful task. Given a ...
Comments