Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm.

Area of Science:

• Network Science
• Information Diffusion
• Machine Learning

Background:

• Information spreads through complex networks, but their structures are often hidden.
• Observed diffusion processes, known as cascades, leave traces that may reveal network topology.
• Existing methods for inferring networks from cascade data lack a thorough theoretical understanding.

Purpose of the Study:

• To investigate the problem of inferring hidden network structures from observed cascades.
• To develop a theoretical framework for network inference under general continuous-time diffusion models.
• To determine the conditions and number of cascades required for accurate network recovery.

Main Methods:

• Utilized an L1-regularized likelihood maximization framework for network inference.
• Analyzed a general family of continuous-time diffusion models.
• Developed an efficient soft-thresholding inference algorithm.

Main Results:

• The proposed framework can recover the correct network structure with high probability.
• Network recovery is successful when the cascade sampling satisfies an incoherence condition.
• The required number of cascades is O(d^3 log N), where d is the maximum node out-degree and N is the number of nodes.

Conclusions:

• The study provides a theoretical foundation for network structure inference from cascade data.
• The developed framework offers provable guarantees for network recovery.
• The proposed soft-thresholding algorithm demonstrates practical effectiveness and outperforms existing methods.