Research On The Algorithm Of Maximizing Influence Based On Weighted Coritivity

The social network model can be equated to abstract representation of the real complex systems,the nodes represent system elements and the edges social relationships between elements.And the key elements in the network are called influential nodes.The determination of key nodes provides a solution for correspondence problems,such as achieving the best communication effect with minimum costs in network marketing,or rapidly and effectively locating the source of information dissemination in public opinion control.This thesis aims to solve the problem of maximizing influence and the research target refers to the selection of several seed nodes as appropriate source of transmission for influence communication from a network,so as to infect most extensive nodes with seed sets when the communication gets stable.The existing solutions include heuristic algorithm and greedy algorithm,and the heuristic algorithm is simple but of strong pertinence;and greedy algorithm has high accuracy in many different types of topology networks,but has a high time complexity.The core of system is directly as a seed set in the existing influence maximization algorithm based on the core of the system in the heuristic algorithms,which using the connected component and the cut point set to measure the capability of the node set to maintain network connectivity,but there is no research for the effect the local topology to the transmission of the influence,and seed set size is fixed and can not to distinguish the influence of seed node.As the advantages and disadvantages of existing measurement were analyzed,the influence maximization problem was solved by the core and coritivity theory in this thesis.Node coritivity was defined based on the theory of core and coritivity,and the distance between nodes and the core of network was measured by the node coritivity difference.In order to study the influence of the network topology to the key elements,the local clustering coefficient and degree of correlation between actual influence and node were analyzed using the actual data in this thesis,which defined the nodes of the weighted clustering coefficient as a measure of network topology characteristics.Weighted coritivity(coritivity based on weighted clustering coefficient,CBWCC),as an index measuring node influence,was defined by introducing to the node coritivity difference in the thesis,which designed and implemented social network influence maximization algorithm based on weighted coritivity,including the normal subcore and the core algorithm,which was respectively achieved by improving them from core and coritivity theory,effectively reducing the algorithm running time.Weighted coritivity influence maximization algorithm was proposed in this thesis for a sort of all nodes,and output the seed set of the specified size.In order to verify the validity of the weighted coritivity algorithm,the simulation tools based on the SIR model was implemented in this thesis,and the spread of algorithm performance is verified on the public data sets,and the degree centrality(DC),betweenness centrality(BC)and closeness centrality(CC)method were compared.The experimental results show that the weighted coritivity seed set got the optimal spreading influence,and can realize a wide range of influence in the network of various types of topology,and this algorithm has more advantages in a heterogeneous network or seed set on a much larger scale.