New results on spread of influence in social networks

• Main Author: Lee, Zhuo Qi
• Other Authors: Hsu Wen Jing
• Format: Theses and Dissertations
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Computer science and engineering::Information systems::Database management; DRNTU::Engineering::Computer science and engineering::Information systems::Information systems applications
• Online Access: http://hdl.handle.net/10356/62317
• Institution: Nanyang Technological University

With the proliferation of Online Social Networks and increasing availability of data, much research is being conducted to uncover the structural and dynamic patterns of social networks and the interplays between them. For instance, social networks are found to exhibit small-world network properties, and information diffusion phenomena on social networks are fundamentally derived from their topological properties. This thesis presents my results on the spread of influence in social networks which include both microscopic and macroscopic aspects. A detailed understanding of influence diffusion process is crucial for better prediction of disease outbreaks or words-of-mouth marketing effects. For most applications in this area, the task of identifying important nodes is also critical. Such knowledge is ultimately essential for decision making and resource management. My contributions are three-fold. In the first part, I analyze in detail the speed of spreading influences by applying the random walk model. I show that the Mean First Passage Time (MFPT) of a node can be estimated effectively and efficiently by using its local connectivity information. I also present an empirical study that relates MFPT to the Diffusion Centrality which has been found to be reflective of an individual's influential power. Through experiments, I show that the MFPTs exhibit significant correlation with respect to Diffusion Centrality especially when the random walker is inclined to visit neighbours that are better connected. In the context of spreading influences, the finding suggests that MFPT is indeed fundamental to the spread of influences; moreover, such influences are more likely derived from the preferential adoption of opinions of better-connected acquaintances. In contrast, according to the conventional model for the spread of influence, all individuals are equally weighted in spreading influences. To further explore these findings, in the second part, I consider an enhanced influence spread model, called the Preferential Voter Model (PVM), in which the opinion of a well-connected individual is weighed more heavily. I analyze the condition under which a highly connected individual can be reached more quickly in PVM as compared to the classical voter model. The result suggests that it is wise to solicit help from individuals who have a high number of social links for spreading influences, because they not only can help maximize the coverage of spread, but also can help reduce the time for spreading the influence. While individual highly-connected people can help spread influences, they also tend to be mutually connected in a social network. Therefore, relying solely on highly connected individuals to spread influences may not be the most cost-effective strategy. Thus, in the third part, I study the issue of controlling both the cost and coverage of spreading influence in social networks. Specifically, I focus on the problem of selecting a minimal set of individuals to initiate the news dissemination such that a desired portion of individuals in the network will be informed of the news within a given time limit, while offering a guarantee on the probability of achieving the coverage requirement. I show that, unfortunately, the problem is NP-hard, moreover, the coverage probability is not a submodular function, and hence the conventional approaches that exploit the submodularity property cannot be applied directly. Nevertheless, I present an approximation algorithm that can provably guarantee the cost of the solution to be within a multiplicative and additive factor of an optimal set. Empirical results show that the new algorithm indeed significantly outperforms baseline approaches in real world networks.