Finding lasting dense subgraphs

DOI10.1007/S10618-018-0602-XMaRDI QIDQ2218373zbMATH OpenOpenAlexWikidataFDO

Authors Konstantinos Semertzidis, Evaggelia Pitoura, Evimaria Terzi, Panayiotis Tsaparas

Publication date 15 January 2021

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.05440

zbMATH Keywords

social networksdense subgraphsgraph history

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Abstract: Graphs form a natural model for relationships and interactions between entities, for example, between people in social and cooperation networks, servers in computer networks, or tags and words in documents and tweets. But, which of these relationships or interactions are the most lasting ones? In this paper, we study the following problem: given a set of graph snapshots, which may correspond to the state of an evolving graph at different time instances, identify the set of nodes that are the most densely connected in all snapshots. We call this problem the Best Friends For Ever (BFF) problem. We provide definitions for density over multiple graph snapshots, that capture different semantics of connectedness over time, and we study the corresponding variants of the BFF problem. We then look at the On-Off BFF (O^2BFF) problem that relaxes the requirement of nodes being connected in all snapshots, and asks for the densest set of nodes in at least $k$ of a given set of graph snapshots. We show that this problem is NP-complete for all definitions of density, and we propose a set of efficient algorithms. Finally, we present experiments with synthetic and real datasets that show both the efficiency of our algorithms and the usefulness of the BFF and the O^2BFF problems.

Recommendations

• On Finding Dense Subgraphs
• Top-\(k\) overlapping densest subgraphs
• Dense subgraphs on dynamic networks
• Finding densest \(k\)-connected subgraphs
• Fast algorithms for constrained graph density problems

Cites work

• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• Algorithm Theory - SWAT 2004
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Greedily Finding a Dense Subgraph
• On Finding Dense Subgraphs
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

Cited in

(4)

• Generalized core maintenance of dynamic bipartite graphs
• Graph signatures: identification and optimization
• Finding dense subgraphs with maximum weighted triangle density
• Finding conserved low-diameter subgraphs in social and biological networks

This page was built for publication: Finding lasting dense subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218373)