Introduction
As social networks scale to millions of nodes and billions of edges, traditional graph algorithms—such as those used for influence maximization or community detection—encounter significant computational bottlenecks. Network coarsening has emerged as a vital technique to address this, aiming to reduce a graph's size by merging similar nodes into "supernodes" while preserving the original network's fundamental properties.
However, existing coarsening methods typically fall into two categories: static methods that rely solely on structural topology (who is connected to whom) and data-driven methods that rely on information cascades (how information actually flows). Static methods often ignore real-world user behavior, while purely data-driven methods are sensitive to noise and data sparsity. This paper introduces Semi-NetCoarsen, a framework that integrates both structural and dynamic data into a unified, mathematically sound model.
The Semi-NetCoarsen Framework
The core innovation of Semi-NetCoarsen is its treatment of coarsening as a joint optimization problem. It simultaneously minimizes graph regularization to keep structurally connected nodes together and maximizes the likelihood of information cascades to group nodes that exhibit similar activation patterns over time.
As illustrated in Figure 1, the framework models the likelihood of one node being merged into another based on the temporal delay between their activations in a cascade. By using an exponential distribution for these time delays, the model can effectively identify which connections are truly influential versus those that are merely structural artifacts.
Optimization and Implementation
A significant challenge in combining structural and dynamic data is the resulting mathematical complexity, which often leads to non-convex optimization problems. The authors overcome this by carefully formulating the node label distribution, proving that their objective function is convex. This allows for the use of the Accelerated Proximal Gradient (APG) algorithm, ensuring efficient convergence to a global optimum.
Once nodes are grouped, the algorithm maps them to supernodes and recalculates edge weights. This mapping is designed to ensure that the coarsened representation remains a faithful proxy for the original network's influence properties, allowing downstream tasks to be performed on a much smaller graph.
Experimental Evaluation
The researchers evaluated Semi-NetCoarsen using synthetic datasets (Kronecker and Forest Fire graphs) and a real-world Twitter dataset comprising approximately 288,000 nodes and 2.6 million information cascades.
Accuracy and Robustness
In the Twitter dataset, Semi-NetCoarsen demonstrated superior accuracy, achieving an influence spread error rate of just 2.14%. This significantly outperformed purely data-driven methods (9.11% error) and purely structural methods (18.02% error). The framework remained stable across various coarsening rates, from 30% to 70% reduction in graph size.
Computational Efficiency
The most dramatic result was the speedup achieved in downstream tasks. When performing influence maximization—identifying the most effective seeds for a viral campaign—the coarsened network enabled a 100x speedup compared to running the same algorithms on the full-sized original graph.
As shown in Figure 5, the running time for the coarsened network (represented by the bottom-most line) is orders of magnitude lower than that of traditional baselines like PMIA, even as the number of seeds increases.
Conclusion
Semi-NetCoarsen represents a major step forward in network analysis by recognizing that user behavior is as critical as network structure. While the initial coarsening process requires an upfront computational investment, the resulting efficiency gains for downstream analysis are transformative. Future work may explore applying this coarsened representation to other complex tasks such as link prediction and community detection.
Summary updated