research-article

Anchored Densest Subgraph

Authors:

Lijun ChangAuthors Info & Claims

SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data

Pages 1200 - 1213

https://doi.org/10.1145/3514221.3517890

Published: 11 June 2022 Publication History

Abstract

Given a graph, densest subgraph search reports a single subgraph that maximizes the density (i.e., average degree). To diversify the search results without imposing rigid constraints, this paper studies the problem of anchored densest subgraph search (ADS). Given a graph, a reference node set S and an anchored node set A with A-R, ADS reports a supergraph of A that maximizes the R-subgraph density ? a density that favors the nodes that are close to S and are not over-popular in comparison with nodes in R. The two levels of localities bring wide applications, as demonstrated by our use cases. For ADS, we propose an algorithm that is local since the complexity is only related to the nodes in S as opposed to the entire graph. Extensive experiments show that our local algorithm for ADS outperforms the global algorithm by up to three orders of magnitudes in time and space consumption; moreover, our local algorithm outperforms existing local community detection solutions in locality, result density, and query processing time and space.

References

[1]

Esra Akbas and Peixiang Zhao. 2017. Truss-based community search: a truss-equivalence based indexing approach. Proceedings of the VLDB Endowment, Vol. 10, 11 (2017), 1298--1309.

Digital Library

[2]

Morteza Alamgir and Ulrike Von Luxburg. 2010. Multi-agent random walks for local clustering on graphs. In 2010 IEEE International Conference on Data Mining. IEEE, 18--27.

Digital Library

[3]

Reid Andersen, Fan Chung, and Kevin Lang. 2006. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE, 475--486.

Digital Library

[4]

Mehdi Azaouzi, Delel Rhouma, and Lotfi Ben Romdhane. 2019. Community detection in large-scale social networks: state-of-the-art and future directions. Social Network Analysis and Mining, Vol. 9, 1 (2019), 1--32.

[5]

B. Bahmani, R. Kumar, and S. Vassilvitskii. 2012. Densest Subgraph in Streaming and MapReduce. Proceedings of the VLDB Endowment (PVLDB), Vol. 5, 5 (2012), 454--465.

Digital Library

[6]

O. D. Balalau, F. Bonchi, T.-H. H. Chan, F. Gullo, and M. Sozio. 2015. Finding Subgraphs with Maximum Total Density and Limited Overlap. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, WSDM 2015, Shanghai, China, February 2--6, 2015. ACM, 379--388.

[7]

Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015. Efficient and effective community search. Data mining and knowledge discovery, Vol. 29, 5 (2015), 1406--1433.

[8]

S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. E. Tsourakakis. 2015. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In Proc. of STOC'15. 173--182.

[9]

Yuchen Bian, Jingchao Ni, Wei Cheng, and Xiang Zhang. 2017. Many heads are better than one: Local community detection by the multi-walker chain. In 2017 IEEE International Conference on Data Mining (ICDM). IEEE, 21--30.

[10]

Yuchen Bian, Yaowei Yan, Wei Cheng, Wei Wang, Dongsheng Luo, and Xiang Zhang. 2018. On multi-query local community detection. In 2018 IEEE international conference on data mining (ICDM). IEEE, 9--18.

[11]

Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, and Niloy Ganguly. 2017. Metrics for community analysis: A survey. ACM Computing Surveys (CSUR), Vol. 50, 4 (2017), 1--37.

Digital Library

[12]

Lijun Chang and Miao Qiao. 2020. Deconstruct Densest Subgraphs. In WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20--24, 2020, Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen (Eds.). ACM / IW3C2, 2747--2753.

[13]

Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs .Springer Series in the Data Sciences.

Digital Library

[14]

M. Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization, Third International Workshop. 84--95.

[15]

Jiyang Chen, Osmar Za"iane, and Randy Goebel. 2009. Local community identification in social networks. In 2009 International Conference on Advances in Social Network Analysis and Mining. IEEE, 237--242.

Digital Library

[16]

Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. Introduction to Algorithms .McGraw-Hill Higher Education.

Digital Library

[17]

Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, and Wei Wang. 2013. Online search of overlapping communities. In Proceedings of the 2013 ACM SIGMOD international conference on Management of data. 277--288.

Digital Library

[18]

M. Danisch, T.-H. H. Chan, and M. Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In Proc. of WWW'17. 233--242.

[19]

Y. Dourisboure, F. Geraci, and M. Pellegrini. 2007. Extraction and classification of dense communities in the web. In Proceedings of the 16th International Conference on World Wide Web, WWW. ACM, 461--470.

[20]

Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. 2015. Efficient Densest Subgraph Computation in Evolving Graphs. In Proc. of WWW'15. 300--310.

Digital Library

[21]

Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020. A survey of community search over big graphs. The VLDB Journal, Vol. 29, 1 (2020), 353--392.

Digital Library

[22]

Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks V. S. Lakshmanan, and Xuemin Lin. 2019. Efficient Algorithms for Densest Subgraph Discovery. PVLDB, Vol. 12, 11 (2019), 1719--1732.

Digital Library

[23]

K. Fountoulakis, M. Liu, D. F. Gleich, and M. W. Mahoney. 2020. Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance. CoRR, Vol. abs/2004.09608 (2020).

[24]

Esther Galbrun, Aristides Gionis, and Nikolaj Tatti. 2016. Top-k overlapping densest subgraphs. Data Min. Knowl. Discov., Vol. 30, 5 (2016), 1134--1165.

Digital Library

[25]

G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. 1989. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM Journal of Computing, Vol. 18, 1 (1989), 30--55.

Digital Library

[26]

D. Gibson, R. Kumar, and A. Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In Proceedings of the 31st International Conference on Very Large Data Bases. ACM, 721--732.

[27]

Aristides Gionis and Charalampos E. Tsourakakis. 2015. Dense Subgraph Discovery: KDD 2015 tutorial. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10--13, 2015, Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams (Eds.). ACM, 2313--2314.

[28]

A. V. Goldberg. 1984. Finding a Maximum Density Subgraph. Technical Report UCB/CSD-84--171. EECS Department, University of California, Berkeley.

[29]

Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 1311--1322.

Digital Library

[30]

Yasushi Kawase, Yuko Kuroki, and Atsushi Miyauchi. 2019. Graph Mining Meets Crowdsourcing: Extracting Experts for Answer Aggregation. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10--16, 2019, Sarit Kraus (Ed.). ijcai.org, 1272--1279.

[31]

Samir Khuller and Barna Saha. 2009. On Finding Dense Subgraphs. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009, Proceedings, Part I, Vol. 5555. 597--608.

[32]

Jérôme Kunegis. 2013. KONECT -- The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion. 1343--1350. http://dl.acm.org/citation.cfm?id=2488173

[33]

V. E. Lee, N. Ruan, R. Jin, and C. C. Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. In Managing and Mining Graph Data. 303--336.

[34]

Jure Leskovec, Lada A Adamic, and Bernardo A Huberman. 2007. The dynamics of viral marketing. ACM Transactions on the Web (TWEB), Vol. 1, 1 (2007), 5--es.

Digital Library

[35]

J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data .

[36]

Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V. S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. 2020. Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14--19, 2020. 1051--1066.

Digital Library

[37]

Stefanie Muff, Francesco Rao, and Amedeo Caflisch. 2005. Local modularity measure for network clusterizations. Physical Review E, Vol. 72, 5 (2005), 056107.

[38]

L. Orecchia and Z. A. Zhu. 2014. Flow-Based Algorithms for Local Graph Clustering. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5--7, 2014, C. Chekuri (Ed.). SIAM, 1267--1286.

[39]

Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. 2015. Locally Densest Subgraph Discovery. In Proc. of KDD'15. 965--974.

Digital Library

[40]

Jing Shan, Derong Shen, Tiezheng Nie, Yue Kou, and Ge Yu. 2016. Searching overlapping communities for group query. World Wide Web, Vol. 19, 6 (2016), 1179--1202.

Digital Library

[41]

Bintao Sun, Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. 2020. KClist+: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs. Proc. VLDB Endow., Vol. 13, 10 (2020), 1628--1640.

Digital Library

[42]

Nikolaj Tatti and Aristides Gionis. 2013. Discovering Nested Communities. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23--27, 2013, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 8189), Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný (Eds.). Springer, 32--47.

[43]

N. Tatti and A. Gionis. 2015a. Density-friendly Graph Decomposition. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18--22, 2015. ACM, 1089--1099.

Digital Library

[44]

N. Tatti and A. Gionis. 2015b. Density-friendly Graph Decomposition. In Proc. of WWW'15. 1089--1099.

[45]

Charalampos E. Tsourakakis. 2015. The K-clique Densest Subgraph Problem. In Proc. of WWW'15. 1122--1132.

Digital Library

[46]

Elena Valari, Maria Kontaki, and Apostolos N. Papadopoulos. 2012a. Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections. In Scientific and Statistical Database Management - 24th International Conference, SSDBM 2012, Chania, Crete, Greece, June 25--27, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7338), Anastasia Ailamaki and Shawn Bowers (Eds.). Springer, 213--230.

[47]

E. Valari, M. Kontaki, and A. N. Papadopoulos. 2012b. Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections. In Proc. of SSDBM'12. 213--230.

[48]

Twan Van Laarhoven and Elena Marchiori. 2016. Local network community detection with continuous optimization of conductance and weighted kernel k-means. The Journal of Machine Learning Research, Vol. 17, 1 (2016), 5148--5175.

[49]

Nate Veldt, Christine Klymko, and David F Gleich. 2019. Flow-based local graph clustering with better seed set inclusion. In Proceedings of the 2019 SIAM International Conference on Data Mining. SIAM, 378--386.

[50]

Yubao Wu, Yuchen Bian, and Xiang Zhang. 2016. Remember where you came from: on the second-order random walk based proximity measures. Proceedings of the VLDB Endowment, Vol. 10, 1 (2016), 13--24.

Digital Library

[51]

Yubao Wu, Ruoming Jin, Jing Li, and Xiang Zhang. 2015. Robust local community detection: on free rider effect and its elimination. Proceedings of the VLDB Endowment, Vol. 8, 7 (2015), 798--809.

Digital Library

[52]

Yubao Wu, Xiang Zhang, Yuchen Bian, Zhipeng Cai, Xiang Lian, Xueting Liao, and Fengpan Zhao. 2018. Second-order random walk-based proximity measures in graph analysis: formulations and algorithms. The VLDB Journal, Vol. 27, 1 (2018), 127--152.

Digital Library

Cited By

Zhou YGuo QFang YMa C(2024)A Counting-based Approach for Efficient k-Clique Densest Subgraph DiscoveryProceedings of the ACM on Management of Data10.1145/36549222:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654922
Lanciano TMiyauchi AFazzone ABonchi F(2024)A Survey on the Densest Subgraph Problem and its VariantsACM Computing Surveys10.1145/365329856:8(1-40)Online publication date: 30-Apr-2024
https://dl.acm.org/doi/10.1145/3653298
Dai YQiao MLi R(2024)On Density-based Local Community SearchProceedings of the ACM on Management of Data10.1145/36515892:2(1-25)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651589
Show More Cited By

Index Terms

Anchored Densest Subgraph
1. Information systems
  1. Information systems applications
    1. Data mining
      1. Clustering
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Sandwiching a densest subgraph by consecutive cores

In this paper, we show that in the random graph Gn,c/n, with high probability, there exists an integer kï such that a subgraph of Gn,c/n, whose vertex set differs from a densest subgraph of Gn,c/n by Olog2n vertices, is sandwiched by the kï and the kï +...
On the densest k-subgraph problems
The K-clique Densest Subgraph Problem
WWW '15: Proceedings of the 24th International Conference on World Wide Web

Numerous graph mining applications rely on detecting subgraphs which are large near-cliques. Since formulations that are geared towards finding large near-cliques are hard and frequently inapproximable due to connections with the Maximum Clique problem, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data

June 2022

2597 pages

ISBN:9781450392495

DOI:10.1145/3514221

General Chair:
Zachary Ives
University of Pennsylvania (USA)
,
Program Chairs:
Angela Bonifati
Lyon 1 University (France)
,
Amr El Abbadi
University of California, Santa Barbara (USA)

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SIGMOD/PODS '22

Sponsor:

SIGMOD

SIGMOD/PODS '22: International Conference on Management of Data

June 12 - 17, 2022

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
534
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)8

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou YGuo QFang YMa C(2024)A Counting-based Approach for Efficient k-Clique Densest Subgraph DiscoveryProceedings of the ACM on Management of Data10.1145/36549222:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654922
Lanciano TMiyauchi AFazzone ABonchi F(2024)A Survey on the Densest Subgraph Problem and its VariantsACM Computing Surveys10.1145/365329856:8(1-40)Online publication date: 30-Apr-2024
https://dl.acm.org/doi/10.1145/3653298
Dai YQiao MLi R(2024)On Density-based Local Community SearchProceedings of the ACM on Management of Data10.1145/36515892:2(1-25)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651589
Huang YGleich DVeldt NChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized MethodsProceedings of the ACM Web Conference 202410.1145/3589334.3645624(881-892)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645624
Teng SXie JZhang FLu CFang JWang KChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Optimizing Network Resilience via Vertex AnchoringProceedings of the ACM Web Conference 202410.1145/3589334.3645465(606-617)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645465
He YWang KZhang WLin XZhang Y(2023)Scaling Up k-Clique Densest Subgraph DetectionProceedings of the ACM on Management of Data10.1145/35889231:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588923
Trung TChang LLong NYao KThanh Binh H(2023)Verification-Free Approaches to Efficient Locally Densest Subgraph Discovery2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00008(1-13)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00008

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents