The identification of influential spreaders and communities in complex networks

Abstract

This thesis deals with two main research topics in the field of complex network science, including the identification of influential spreaders from the view of nodes and their community discovery from the view of groups of nodes. It aims at understanding the mechanism of a small number of initial nodes known as information sources leading to wide information propagation in social networks. The discovery of communities that these spreaders belong to is another key factor of identifying influential spreaders. Heterogeneous community detection is a vital step towards the understanding of network topological structures and propagation dynamics. These two questions are not isolated but have certain relationship in our study. In this thesis, we have made the following novel contributions. There are a small number of vital nodes which will lead to wide propagation if they are selected as spreaders at the very beginning. The previous method VoteRank is limited because some of the spreaders are clustered in one community. Thus in this thesis, a novel approach ComVote is proposed to uncover multiple influential spreaders. Further experimental study on real networks shows that in Susceptible-Infected-Recovered (SIR) propagation, ComVote outperforms existing methods including VoteRank, CI (Collective Influence), H-index, K-shell and etc. on the final affected scale in SIR. But it also has limitations in the case that the influential spreaders are not connected with each other. Furthermore, VoteRank is merely applied to unweighted networks. A new approach WVoteRank is proposed to find multiple spreaders on weighted networks. WVoteRank is generalised to deal with both unweighted and weighted networks by considering both degree and weight in the voting process. Experimental studies in the present research on synthetic and real networks show that in the context of Susceptible-Infected Recovered (SIR) propagation, WVoteRank outperforms existing methods such as weighted H-index, weighted K-shell, weighted degree centrality and weighted betweenness centrality on the final affected scale. The improvement of final affected scale is as much as 8.96%. In social networks, communities are the natural partition of groups of nodes of the underlying networks where nodes within the same group are closely connected while the edges between different groups are loosely connected. This thesis defines overlapping communities as belonging to such groups where one node can belong to more than one group. Chen et al. firstly proposed a community game (Game) to study this problem. In this thesis, we have investigated how similar vertices affect the formation of the community game. The Adamic-Adar Index (AA Index) has been employed to define the new utility function in chapter 4. This result implicates that ‘friend circles of friends’ of Facebook are valuable to understand overlapping community partition. Many real bipartite networks are naturally divided into two-mode communities including user-item bipartite communities in e-commerce, user-news bipartite communities in personalized news web sites and etc. In the present research, a two-mode community detection algorithm termed BiAttractor was formulated. It is based on distance dynamics model Attractor proposed by Shao et al. with extension from unipartite to bipartite networks. This new idea makes clear assumptions in linear time complexity O(|E|) in sparse networks, where |E| is the number of edges. Experiments in the present research on synthetic networks demonstrate it is capable to overcome resolution limit compared with other existing methods. Further study in the present research on real networks shows that BiAttractor has excellent accuracy compared with other existing methods and it is fast to deal with large-scale networks with millions of nodes and edges. Finally, the influential spreaders during the Malaysian General Election in 2013 (MGE2013) were investigated. It was found that representative of political party located at the center of the propagation network was the winner of the presidential election. It was also found that a number of non-politicians also significantly influenced the election because they located at the central area of the Twitter propagation sphere. This new point of view also supports the Jurgen Habermass ideal of the public sphere, especially in the General Election of Malaysia, a sphere that permits citizens to interact, and debate on the public issues without fear of political powers. In this thesis, influential spreaders are studied to uncover the mechanisms governing the information propagation on complex networks. Overlapping communities and two-mode communities on bipartite networks are investigated to suggest new methods to explain the formation of communities. Studies on influential spreaders and community partitions shed light on future study of patterns and dynamics of complex networks.

Date of Award	10 Nov 2018
Original language	English
Awarding Institution	Univerisity of Nottingham
Supervisor	Eugene Ch'ng (Supervisor), J. M. Garibaldi (Supervisor) & Simon See (Supervisor)