Research Of Influence Maximization Algorithm Based On Node Density And Community Structure

With the spread of Internet and big data research and applications,influence propagation in networks becomes one of hot topics in the field of social network analysis in recent years.The essence of networks is graphs,which are composed of vertices and edges,the vertices represent the objects involved in the problem domain,and the edges represent the interactions or relations between vertices.Influence Maximization(IM),which selects the set of k seeds from a network,aims to maximize the expected number of influenced nodes.Due to its immense application potential and enormous technical challenges,IM has been extensively studied.Complex network models simplify many real-world problems.In this thesis,we present two new heuristic methods named DBIM(Density Based Influence Maximization)which based on density of the node and IMCAN(Influence Maximization based on Community And Second-hop Neighbors)which based on community structure and second-hop neighbors.(1)Density based influence maximization.This algorithm introduces density to represent the influence of nodes.In DBIM,we firstly sum the reciprocal of degree of neighbors to each node in network.Nodes with higher density has bigger influence.Then we get the minimum distance between the node with its neighbors which has a higher density for each node.We want this distance to be large enough to minimize the influence overlap.Finally,we multiply the density by the distance for each node to get the score of influence.We extract the seeds by selecting the nodes with the top-k scores.(2)Influence maximization based on community and second-hop neighbors.This algorithm takes into account the impacts of both community structure and second-hop neighbors to the influence spreads of each node to select the seed nodes from the network.Firstly,We conducted community detection on the network based on Fast Q and LPA to get many community structures to reduce the impact of community detection algorithm problems.Then We calculate a influence score for each node by considering its influence among its first-and second-order neighbors and the average number of its adjacent communities.Secondly,We choose the node with highest score as seed.we remove the direct neighbors of the selected seed from the network,and have the influence of the seed's second-order neighbors being attenuated by a factor.Then,we select the node with the largest score as the next seed.This process is repeated until all the seed nodes are obtained.We conducted extensive experiments on some real-world networks,and compared the results with with those of some state-of-the-art algorithms.The experimental results show that both DBIM and IMCAN can obtain the seed nodes with larger influence propagation ability.Specifically,DBIM suits for use in small-or mediate-scaled networks,and IMCAN can get better influence spreads in larger scaled networks.