Critical individuals in dynamic population networks.

摘要

Diffusion of contaminants, diseases, rumors, fads, and many other dynamic processes typically take place through a network of interacting entities. One fundamental question in the context of diffusion, particularly in social networks is: which entities in a network are critical for a given diffusion process? For instance, these critical entities could be individuals to whom free products should be given in a network so that the adoption of the product is maximized. Or, individuals in a population who should be vaccinated so that the spread of a virus or a contaminant is minimized. Or, leaders in a network that are critical for initiating a mass movement. In my research, I address the question of finding critical individuals for diffusion in networks in the context of network theory, graph mining, machine learning, and social network analysis. My research focuses on two complimentary optimization goals: maximization and minimization of the extent of the resulting extent of diffusion. For diffusion maximization, I analyze: 1. the hardness of diffusion maximization in dynamic networks; 2. the impact of structural changes in prediction of diffusion in networks; 3. the global structural indicators for measuring the effectiveness of various diffusion maximization methods in both static and dynamic networks. For diffusion minimization, I develop simple, practical, and locally computable heuristics for identifying critical nodes in dynamic networks. In this work, I study explicitly dynamic or time evolving networks instead of traditional static or aggregate representation of networks. Lastly, for rigorous analysis of the stochastic diffusion optimization problem, realistic network generative models are very crucial. I present a truly dynamic statistical generative network model that captures membership, formation, and fluidity of community membership and the resulting structure of interactions.