research-article

Open access

Finding Densest Subgraphs with Edge-Color Constraints

Authors:

Lutz Oettershagen,

Aristides GionisAuthors Info & Claims

WWW '24: Proceedings of the ACM Web Conference 2024

Pages 936 - 947

https://doi.org/10.1145/3589334.3645647

Published: 13 May 2024 Publication History

Abstract

We consider a variant of the densest subgraph problem in networks with single or multiple edge attributes. For example, in a social network, the edge attributes may describe the type of relationship between users, such as friends, family, or acquaintances, or different types of communication. For conceptual simplicity, we view the attributes as edge colors. The new problem we address is to find a diverse densest subgraph that fulfills given requirements on the numbers of edges of specific colors. When searching for a dense social network community, our problem will enforce the requirement that the community is diverse according to criteria specified by the edge attributes. We show that the decision versions for finding exactly, at most, and at least h colored edges densest subgraph, where h is a vector of color requirements, are NP-complete, for already two colors. For the problem of finding a densest subgraph with at least h colored edges, we provide a linear-time constant-factor approximation algorithm when the input graph is sparse. On the way, we introduce the related at least h (non-colored) edges densest subgraph problem, show its hardness, and also provide a linear-time constant-factor approximation. In our experiments, we demonstrate the efficacy and efficiency of our new algorithms.

Supplemental Material

MP4 File

video presentation

Download
1430.33 MB

MP4 File

Supplemental video

Download
10.13 MB

References

[1]

Aris Anagnostopoulos, Luca Becchetti, Adriano Fazzone, Cristina Menghini, and Chris Schwiegelshohn. 2020. Spectral relaxations and fair densest subgraphs. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 35--44.

Digital Library

[2]

Reid Andersen and Kumar Chellapilla. 2009. Finding dense subgraphs with size bounds. In International workshop on algorithms and models for the web-graph. Springer, 25--37.

Digital Library

[3]

Albert Angel, Nick Koudas, Nikos Sarkas, Divesh Srivastava, Michael Svendsen, and Srikanta Tirthapura. 2014. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. The VLDB journal, Vol. 23 (2014), 175--199.

[4]

Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, and Takeshi Tokuyama. 2000. Greedily finding a dense subgraph. Journal of algorithms, Vol. 34, 2 (2000), 203--221.

Digital Library

[5]

Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049 (2003).

[6]

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. 2010. Detecting high log-densities: an O (n $1/4$) approximation for densest k-subgraph. In Proceedings of the forty-second ACM symposium on Theory of computing. 201--210.

Digital Library

[7]

Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting densest subgraphs without flow computations. In Proceedings of The Web Conference 2020. 573--583.

Digital Library

[8]

Alessio Cardillo, Jesús Gómez-Gardenes, Massimiliano Zanin, Miguel Romance, David Papo, Francisco del Pozo, and Stefano Boccaletti. 2013. Emergence of network features from multiplexity. Scientific reports, Vol. 3, 1 (2013), 1344.

[9]

Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In International workshop on approximation algorithms for combinatorial optimization. Springer, 84--95.

[10]

Chandra Chekuri, Kent Quanrud, and Manuel R Torres. 2022. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1531--1555.

[11]

Jie Chen and Yousef Saad. 2010. Dense subgraph extraction with application to community detection. IEEE Transactions on knowledge and data engineering, Vol. 24, 7 (2010), 1216--1230.

Digital Library

[12]

Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM J. Comput., Vol. 32, 5 (2003), 1338--1355.

Digital Library

[13]

Manlio De Domenico, Vincenzo Nicosia, Alexandre Arenas, and Vito Latora. 2015. Structural reducibility of multilayer networks. Nature communications, Vol. 6, 1 (2015), 6864.

[14]

Mark E. Dickison, Matteo Magnani, and Luca Rossi. 2016. Multilayer Social Networks. Cambridge University Press.

[15]

Yon Dourisboure, Filippo Geraci, and Marco Pellegrini. 2007. Extraction and classification of dense communities in the web. In Proceedings of the 16th international conference on World Wide Web. 461--470.

Digital Library

[16]

Uriel Feige and Michael Seltser. 1997. On the densest k-subgraph problem.

[17]

Amita Gajewar and Atish Das Sarma. 2012. Multi-skill collaborative teams based on densest subgraphs. In Proceedings of the 2012 SIAM international conference on data mining. SIAM, 165--176.

[18]

Edoardo Galimberti, Francesco Bonchi, and Francesco Gullo. 2017. Core decomposition and densest subgraph in multilayer networks. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 1807--1816.

Digital Library

[19]

David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st international conference on Very large data bases. 721--732.

Digital Library

[20]

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. 2313--2314.

Digital Library

[21]

Andrew V Goldberg. 1984. Finding a maximum density subgraph. (1984).

[22]

Mark S Granovetter. 1973. The strength of weak ties. American journal of sociology, Vol. 78, 6 (1973), 1360--1380.

[23]

Farnoosh Hashemi, Ali Behrouz, and Laks VS Lakshmanan. 2022. FirmCore decomposition of multilayer networks. In Proceedings of the ACM Web Conference 2022. 1589--1600.

Digital Library

[24]

Julia Heidemann, Mathias Klier, and Florian Probst. 2012. Online social networks: A survey of a global phenomenon. Computer networks, Vol. 56, 18 (2012), 3866--3878.

[25]

Xinyu Huang, Dongming Chen, Tao Ren, and Dongqi Wang. 2021. A survey of community detection methods in multilayer networks. Data Mining and Knowledge Discovery, Vol. 35 (2021), 1--45.

Digital Library

[26]

Lorenzo Isella, Juliette Stehlé, Alain Barrat, Ciro Cattuto, Jean-Francc ois Pinton, and Wouter Van den Broeck. 2011. What's in a crowd? Analysis of face-to-face behavioral networks. Journal of theoretical biology, Vol. 271, 1 (2011), 166--180.

[27]

Ravindran Kannan and V Vinay. 1999. Analyzing the structure of large graphs. Universit"at Bonn. Institut für Ökonometrie und Operations Research.

[28]

Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. In International colloquium on automata, languages, and programming (ICALP). 597--608.

[29]

Mikko Kivel"a, Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter. 2014. Multilayer networks. Journal of complex networks, Vol. 2, 3 (2014), 203--271.

[30]

Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ashesh Rambachan. 2018. Algorithmic fairness. In Aea papers and proceedings, Vol. 108. American Economic Association 2014 Broadway, Suite 305, Nashville, TN 37203, 22--27.

[31]

Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. 2023. A survey on the densest subgraph problem and its variants. arXiv preprint arXiv:2303.14467 (2023).

[32]

Victor E Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. Managing and mining graph data (2010), 303--336.

[33]

Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Signed networks in social media. In Proceedings of the SIGCHI conference on human factors in computing systems. 1361--1370.

Digital Library

[34]

Michael Ley. 2002. The DBLP computer science bibliography: Evolution, research issues, perspectives. In International symposium on string processing and information retrieval. Springer, 1--10.

Digital Library

[35]

Matteo Magnani, Barbora Micenkova, and Luca Rossi. 2013. Combinatorial analysis of multiple networks. arXiv preprint arXiv:1303.4986 (2013).

[36]

Shira Mitchell, Eric Potash, Solon Barocas, Alexander D'Amour, and Kristian Lum. 2021. Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application, Vol. 8 (2021), 141--163.

[37]

Atsushi Miyauchi, Tianyi Chen, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis. 2023. Densest Diverse Subgraphs: How to Plan a Successful Cocktail Party with Diversity. 1710--1721.

[38]

Syama Sundar Rangapuram, Thomas Bühler, and Matthias Hein. 2013. Towards realistic team formation in social networks based on densest subgraphs. In Proceedings of the 22nd international conference on World Wide Web. 1077--1088.

Digital Library

[39]

Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, and Xiao-Ning Zhang. 2010. Dense subgraphs with restrictions and applications to gene annotation graphs. In Research in Computational Molecular Biology (RECOMB). 456--472.

[40]

Chengcheng Shao, Pik-Mai Hui, Lei Wang, Xinwen Jiang, Alessandro Flammini, Filippo Menczer, and Giovanni Luca Ciampaglia. 2018. Anatomy of an online misinformation network. Plos one, Vol. 13, 4 (2018).

[41]

Stavros Sintos and Panayiotis Tsaparas. 2014. Using strong triadic closure to characterize ties in social networks. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 1466--1475.

Digital Library

[42]

Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. 2015. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 conference on empirical methods in natural language processing. 1499--1509.

[43]

Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. 2013. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 104--112.

Digital Library

[44]

Philippe Vanhems, Alain Barrat, Ciro Cattuto, Jean-Francc ois Pinton, Nagham Khanafer, Corinne Régis, Byeul-a Kim, Brigitte Comte, and Nicolas Voirin. 2013. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PloS one, Vol. 8, 9 (2013), e73970.

[45]

Serene WH Wong, Chiara Pastrello, Max Kotlyar, Christos Faloutsos, and Igor Jurisica. 2018. Sdregion: Fast spotting of changing communities in biological networks. In Proceedings of the 24th ACM SIGKDD international conference on Knowledge discovery & data mining. 867--875.

Digital Library

Cited By

Hashemi FBehrouz ABaeza-Yates RBonchi F(2024)A Unified Core Structure in Multiplex Networks: From Finding the Densest Subgraph to Modeling User EngagementProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672011(1028-1039)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672011
Wickrama Arachchi CTatti N(2024)Fair Densest Subgraph Across Multiple GraphsMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70362-1_1(3-19)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70362-1_1

Index Terms

Finding Densest Subgraphs with Edge-Color Constraints
1. Information systems
  1. World Wide Web
    1. Web applications
      1. Social networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Finding densest k-connected subgraphs
Abstract
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an ...
Deconstruct Densest Subgraphs
WWW '20: Proceedings of The Web Conference 2020

In this paper, we aim to understand the distribution of the densest subgraphs of a given graph under the density notion of average-degree. We show that the structures, the relationships and the distributions of all the densest subgraphs of a graph G can ...
Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present 32-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '24: Proceedings of the ACM Web Conference 2024

May 2024

4826 pages

ISBN:9798400701719

DOI:10.1145/3589334

General Chairs:
Tat-Seng Chua
National University of Singapore
,
Chong-Wah Ngo
Singapore Management University
,
Proceedings Chair:
Roy Ka-Wei Lee
Singapore University of Technology and Design
,
Program Chairs:
Ravi Kumar
Google
,
Hady W. Lauw
Singapore Management University

Copyright © 2024 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 May 2024

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ERC Advanced Grant REBOUND
EC H2020 RIA project SoBigData++
Wallenberg AI, Autonomous Systems and Software Program

Conference

WWW '24

Sponsor:

SIGWEB

WWW '24: The ACM Web Conference 2024

May 13 - 17, 2024

Singapore, Singapore

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
186
Total Downloads

Downloads (Last 12 months)186
Downloads (Last 6 weeks)30

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hashemi FBehrouz ABaeza-Yates RBonchi F(2024)A Unified Core Structure in Multiplex Networks: From Finding the Densest Subgraph to Modeling User EngagementProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672011(1028-1039)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672011
Wickrama Arachchi CTatti N(2024)Fair Densest Subgraph Across Multiple GraphsMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70362-1_1(3-19)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70362-1_1

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents