Community-aware network sparsification
Network sparsification aims to reduce the number of edges of a network while maintaining
its structural properties; such properties include shortest paths, cuts, spectral measures, or …
its structural properties; such properties include shortest paths, cuts, spectral measures, or …
On the complexity of community-aware network sparsification
E Herrendorf, C Komusiewicz, N Morawietz… - arXiv preprint arXiv …, 2024 - arxiv.org
Network sparsification is the task of reducing the number of edges of a given graph while
preserving some crucial graph property. In community-aware network sparsification, the …
preserving some crucial graph property. In community-aware network sparsification, the …
Structure-preserving sparsification of social networks
G Lindner, CL Staudt, M Hamann… - Proceedings of the …, 2015 - dl.acm.org
Sparsification reduces the size of networks while preserving structural and statistical
properties of interest. Various sparsifying algorithms have been proposed in different …
properties of interest. Various sparsifying algorithms have been proposed in different …
Structure-preserving sparsification methods for social networks
M Hamann, G Lindner, H Meyerhenke… - Social Network Analysis …, 2016 - Springer
Sparsification reduces the size of networks while preserving structural and statistical
properties of interest. Various sparsifying algorithms have been proposed in different …
properties of interest. Various sparsifying algorithms have been proposed in different …
Network Sparsification via Degree-and Subgraph-based Edge Sampling
Network (or graph) sparsification compresses a graph by removing inessential edges. By
reducing the data volume, it accelerates or even facilitates many downstream analyses. Still …
reducing the data volume, it accelerates or even facilitates many downstream analyses. Still …
An efficient algorithm for unweighted spectral graph sparsification
DG Anderson, M Gu, C Melgaard - arXiv preprint arXiv:1410.4273, 2014 - arxiv.org
Spectral graph sparsification has emerged as a powerful tool in the analysis of large-scale
networks by reducing the overall number of edges, while maintaining a comparable graph …
networks by reducing the overall number of edges, while maintaining a comparable graph …
Why the Metric Backbone Preserves Community Structure
The metric backbone of a weighted graph is the union of all-pairs shortest paths. It is
obtained by removing all edges $(u, v) $ that are not the shortest path between $ u $ and $ v …
obtained by removing all edges $(u, v) $ that are not the shortest path between $ u $ and $ v …
Triangle-aware spectral sparsifiers and community detection
K Sotiropoulos, CE Tsourakakis - Proceedings of the 27th ACM SIGKDD …, 2021 - dl.acm.org
Triangle-aware graph partitioning has proven to be a successful approach to finding
communities in real-world data [8, 40, 51, 54]. But how can we explain its empirical success …
communities in real-world data [8, 40, 51, 54]. But how can we explain its empirical success …
Detecting community structures in social networks by graph sparsification
P Basuchowdhuri, S Sikdar, S Shreshtha… - Proceedings of the 3rd …, 2016 - dl.acm.org
Community structures are inherent in social networks and finding them is an interesting and
well-studied problem. Finding community structures in social networks is similar to locating …
well-studied problem. Finding community structures in social networks is similar to locating …
A Generic Graph Sparsification Framework using Deep Reinforcement Learning
The interconnectedness and interdependence of modern graphs are growing ever more
complex, causing enormous resources for processing, storage, communication, and …
complex, causing enormous resources for processing, storage, communication, and …