Modeling influence diffusion in networks for community detection, resilience analysis and viral marketing

The past decades have seen a fast-growing and dynamic trend of network science and its applications. From the Internet to Facebook, from telecommunications to power grids, from protein interactions to paper citations, networks are everywhere and the network paradigm is pervasive. Network analysis and mining has become an important tool for scientific research and industrial applications to diverse domains. For example, finding communities within social networks enables us to identify groups of densely connected customers who may share similar interests and behaviors and thus generate more effective recommender systems; investigating the supply-network topological structure and growth model improves the resilience of supply networks against disruptions; and modeling influence diffusion in social networks provides insights into viral marketing strategies. However, none of these tasks is trivial. In fact, community detection, resilience analysis, and influence-diffusion modeling are all important challenges in complex networks. My PhD research contributes to these endeavors by exploring the implicit knowledge of connectivity and proximity encoded in the network graph topology.

Our research originated from an attempt to find communities in networks. After carefully examining real-life communities and the features and limitations of a set of widely-used centrality measures, we develop a simple but powerful reachability-based influence-diffusion model. Based upon this model, we propose a new influence centrality and a novel shared-influence-neighbor (SIN) similarity. The former differentiates the comprehensive influence significance more precisely, and the latter gives rise to a refined vertex-pair closeness metric. Then we develop an influence-guided spherical K-means (IGSK) algorithm for community detection. Further, we propose two novel influence-guided label propagation (IGLP) algorithms for finding hierarchical communities in complex networks. Experiments on both real-life networks and synthetic benchmarks demonstrate superior performance of our algorithms in both undirected/directed and unweighted/weighted networks.

Another research topic we investigated is resilience analysis of supply networks.

Supply networks play an important role in product distribution, and survivability is a critical concern in supply-network design and analysis. We exploit the resilience embedded in supply-network topology by exploring the multiple-path reachability of each demand node to other nodes, and propose a novel resilience metric. We also develop new supply-network growth mechanisms that reflect the heterogeneous roles of different types of units in supply networks. We incorporate them into two fundamental network topologies (random-graph topology and scale-free topology), and evaluate the resilience under random disruptions and targeted attacks using the new resilience metric. The experimental results verify the validity of our resilience metric and the effectiveness of our growth model. This research provides a generic framework and important insights into the construction of robust supply networks.

Finally, we investigate activation-based influence-diffusion modeling for viral marketing. One of the fundamental problems in viral marketing is to find a small set of initial adopters who can trigger the largest further adoptions through word-of-mouth-based influence propagation in the network. We propose a novel multiple-path asynchronous threshold (MAT) model, in which we quantitatively measure influence and keep track of its diffusion and aggregation during the diffusion process. Our MAT model captures both direct and indirect influence, influence attenuation along diffusion paths, temporal influence decay, and individual diffusion dynamics. Our work is an important step toward a more realistic diffusion model. Further, we develop two effective and efficient heuristics (IV-Greedy and IV-Community) to tackle the influence-maximization problem. Our experiments on four real-life networks demonstrate their excellent performance in terms of both influence spread and efficiency. Our work provides preliminary but significant insights and implications for diffusion research and marketing practice.