Sparse Multi-Task Learning for Detecting Influential Nodes in an Implicit Diffusion Network

Yingze Wang, Guang Xiang, Shi-Kuo ChangAAAI 2013 · DOI

Introduction

Identifying influential nodes in social networks is a critical task for applications ranging from viral marketing to public health monitoring. Traditional influence models often rely on two restrictive assumptions: the availability of a complete "follow" graph and the treatment of influence as a topic-agnostic, global metric. In reality, network structures are often implicit—driven by content interactions rather than formal links—and influence is highly specialized, where an authority in one domain (e.g., Finance) may have little impact in another (e.g., Gardening).

To address these challenges, we present the Multi-task Sparse Linear Influential Model (MSLIM). MSLIM identifies topic-specific influencers within implicit diffusion networks by leveraging multi-task learning to simultaneously predict information volume across multiple contagions while exploiting similarities between related subjects.

Methodology: The MSLIM Framework

The MSLIM model builds upon the Linear Influence Model (LIM), which estimates the future volume of a contagion based on the historical activity of nodes. MSLIM introduces several key enhancements to handle the complexity of real-world social data.

Multi-Task and Sparse Learning

Unlike previous models that assume static influence, MSLIM allows a node's influence to vary across different contagions. By formulating the problem as a convex optimization task with a sparsity-inducing penalty (combining Frobenius and $l_1/l_2$ mixed-norms), the model automatically selects a minimal set of truly influential nodes for each topic. This multi-task approach ensures that knowledge from similar topics (e.g., "iPhone" and "iPad") is shared, improving the robustness of detection.

Comparison of MSLIM with existing influence models across key features.

Efficient Optimization

To handle large-scale datasets, the authors adapted the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA). By deriving an exact closed-form solution for the proximal mapping step, MSLIM achieves an optimal convergence rate, making it computationally feasible for practical applications. As shown in the comparison above, MSLIM is the only model to simultaneously address implicit networks (WO-NS), multi-contagion scenarios, and temporal dynamics.

Experimental Evaluation

The model was validated using a real-world Twitter dataset comprising 2.6 million tweets from 1,000 users associated with TechCrunch. Latent Dirichlet Allocation (LDA) was employed to extract 50 distinct topics, serving as the "contagions" for the influence analysis.

Performance Metrics

MSLIM significantly outperformed established benchmarks, including In-degree, PageRank, and TwitterRank. In terms of prediction accuracy, MSLIM achieved a Mean Squared Error (MSE) of 13.03, compared to 16.21 for TwitterRank and 20.24 for standard single-task models. Furthermore, the model demonstrated high efficiency, processing the dataset in approximately 170 seconds on a standard PC—only a marginal increase over the simpler, less accurate LIM model.

Key Insights and Geographic Analysis

A significant advantage of MSLIM is its interpretability. The model successfully identified specific personas as leaders in their respective fields, such as marketing managers for "Apple" and financial media accounts for "Finance."

Qualitative analysis also revealed distinct geographic patterns of influence. For instance, "Apple" influencers were concentrated in North America, while "Samsung" influencers showed higher prominence in Europe. Notably, "Startup" influencers were found to be almost exclusively located in Silicon Valley (US West Coast), a pattern visualized in the global distribution of detected nodes.

Global distribution of influential nodes identified by the MSLIM model.

Conclusion and Future Work

MSLIM demonstrates that implicit network data is sufficient for identifying topic-specific influencers when combined with sparse multi-task learning. By moving away from the "known network" assumption, the model provides a more realistic and nuanced view of social influence. Future research will focus on scaling the model to larger node sets and incorporating dynamic time-lags to better capture the varying "influence tails" of different topics.

Summary updated

BibTeX
@inproceedings{wang2013sparse,
  author = {Yingze Wang and Guang Xiang and Shi-Kuo Chang},
  title = {{Sparse Multi-Task Learning for Detecting Influential Nodes in an Implicit Diffusion Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8575},
}
Figure