The Study Of Influencial Nodes And Influence Difussion In A Complex Network

The study of complex network includes a lot of questions: such as identify the influential nodes in a network, link prediction, community detection, influence maximization and so on. For online social network, the research of social influence analysis has been a hot topic in the field of data mining. The rapid developments of large –scale social networks provide us a large amount of data for scientific research. How to identify influential nodes in a network quickly and effectively has become an urgent problem to be solved. This paper aims at node ranking and influence maximization in a social network. The main works of this dissertation are presented as follows.Firstly, a new algorithm for identify the key nodes in a network called DKN is proposed in this paper. DKN algorithm takes the degree of a node, the positions of the node in the network, and its transmission ability into consideration comprehensively. Then use DKN method to measure the importance of a node and tests in different networks comparing with other node ranking methods.Secondly, due to the high time complexity of greedy algorithm and degree heuristic algorithm may lead an overlapping effect when selecting the node in a community, a new algorithm based on K–shell decomposition and degree heuristic algorithm called KDHA is proposed. KDHA algorithm not only solves the influence maximization in a lower time complexity than Greedy algorithm, but also avoids overlapping effect when choosing the initial seed nodes. It also extends the ability of K-shell algorithm in solving the influence maximization problem on multi-nodes.Finally, the experiment was measured in two aspects, the propagation effect and the time complexity. In this paper, KDHA algorithm was compared with Greedy algorithm, random algorithm and degree algorithm in different real social network datasets. Experiments show that KDHA algorithm can reach a better communication effect with a lower time complexity.