Large very dense subgraphs in a stream of edges. (December 2021)

• Record Type: Journal Article
• Authors: Mathieu, Claire; de Rougemont, Michel
• Is Part Of: Network science. Volume 9:Number 4(2021)
• Page Start: 403
• Page End: 424
• Publication Date: 2021-12
• Subjects: dense subgraphs -- clustering -- streaming -- probabilistic analysis -- random graphs -- approximation; Social networks -- Research -- Periodicals; System analysis -- Periodicals; System theory -- Periodicals; Computer science -- Periodicals; 003.72
• DOI: 10.1017/nws.2021.17
• Languages: English
• ISSNs: 2050-1242

Abstract

Abstract: We study the detection and the reconstruction of a large very dense subgraph in a social graph with n nodes and m edges given as a stream of edges, when the graph follows a power law degree distribution, in the regime when $m=O(n. \log n)$ . A subgraph S is very dense if it has $\Omega(|S|^2)$ edges. We uniformly sample the edges with a Reservoir of size $k=O(\sqrt{n}.\log n)$ . Our detection algorithm checks whether the Reservoir has a giant component. We show that if the graph contains a very dense subgraph of size $\Omega(\sqrt{n})$, then the detection algorithm is almost surely correct. On the other hand, a random graph that follows a power law degree distribution almost surely has no large very dense subgraph, and the detection algorithm is almost surely correct. We define a new model of random graphs which follow a power law degree distribution and have large very dense subgraphs. We then show that on this class of random graphs we can reconstruct a good approximation of the very dense subgraph with high probability. We generalize these results to dynamic graphs defined by sliding windows in a stream of edges.