Automated ConNIe: Bridging the Gap in Social Network Topology Inference

TL;DR

Inferring the "hidden" edges of a social network based on information cascades (who posted what and when) is a classic inverse problem. While the ConNIe (Convex Network Inference) algorithm provided a mathematical breakthrough, its reliance on manually tuned parameters made it fragile. This paper introduces a self-tuning framework that uses Perceptron for model classification and PSO for parameter optimization, making network inference feasible when the underlying dynamics are unknown.

The "Black Box" of Information Cascades

In modern social networks (Twitter, WeChat, Weibo), we rarely see the underlying "wiring" of influence. Instead, we see Cascades: Node A posts a message at $t_1$, then Node B posts it at $t_2$. Did A influence B?

Prior works like NETINF attempted to solve this, but struggled with accuracy. ConNIe improved this by framing it as a convex optimization problem with a sparsity penalty ($L_1$-like), but it introduced a new headache: practitioners had to guess the "Sparse Parameter" ($\rho$) and the "Propagation Time Distribution" (e.g., does information decay exponentially or follow a Power Law?). If you guess wrong, your inferred network is essentially noise.

Methodology: The Self-Optimizing Framework

The authors propose a "Pre-processing + Classification + Optimization" pipeline to eliminate manual guesswork.

1. Identifying the Distribution (The Perceptron)

Information flows differently depending on the medium. The authors defined four candidate distributions: Power, Exponential, Uniform, and Weibull. By sorting cascade time differences and using a Perceptron algorithm, they created a classifier that can look at raw observation data and predict which model it follows with 98.3% accuracy.

2. Hunting for Parameters (PSO)

Once the model type is known (e.g., Weibull), we still need the specific shape parameters ($k$, $\lambda$) and the sparsity weight ($\rho$). Since the relationship between these parameters and the network accuracy is non-linear and "black box," the authors employed Particle Swarm Optimization (PSO).

Figure: The fitness function converges after approximately 11 iterations, showing the PSO's ability to find optimal parameters that maximize the similarity between real and reconstructed cascades.

Experimental Insights: Where ConNIe Fails and Succeeds

The paper provides a critical "Ablation-style" look at how different network structures affect inference:

• Scale-Free (BA) Networks: Highly successful. The algorithm excels at finding "hubs."
• Small-World (NW) Networks: Surprisingly, ConNIe performs poorly here. The authors note that the recall is near zero, suggesting the algorithm's inductive bias is heavily skewed toward scale-free structures common in social media.
• Sparsity Sensitivity: As shown below, the choice of $\rho$ is a trade-off between Precision and Recall.

Figure: Variation of Precision, Recall, and MSE across different values of the sparse parameter $\rho$.

Results & Final Takeaway

The framework's performance on BA networks is impressive. On a test with 200 nodes and 1000 edges, the automated framework achieved a Precision of 0.823 and Recall of 0.944, nearly matching "Standard" results where the ground-truth parameters were known.

Critical Analysis: While the framework solves the parameter-tuning issue, its reliance on a pre-defined set of four distributions may be a limitation. Future work could benefit from Non-parametric density estimation to handle even more complex, real-world propagation behaviors. However, for public opinion control and marketing analysis, this represents a significant step toward "Zero-configuration" network inference.