Research On Identifying Node And Edge Importance And Influence Maximization In Complex Networks

In recent years,complex network research has attracted widespread attention from researchers in different fields such as physics,mathematics,chemistry,medicine,biology,computer science,and sociology.The real network is heterogeneous.The roles of different nodes or different edges in the network have great difference in network structure and function.From the perspective of network robustness and vulnerability,whether a node or an edge is important is determined by the change degree of the network connectivity caused by removing the node or the edge.Accurately mining key nodes and key edges in the network can act as not only a defensive strategy by taking a protection of key nodes and key edges of the network to improve the invulnerability of the network,but also an offensive strategy by concentrating attack the key nodes and key edges to achieve greater profits with lower costs.Considering the structural characteristics of complex networks,this paper studies the importance metrics of nodes and edges in complex networks basing on network robustness,and further studies the influence maximization in multi-source information propagation.A complex network node importance identification algorithm based on node bridging features is proposed.The actual networks are featured with large data scale,and the network structures are complex and often change with time.The metrics based on the global information of the network are not adaptive for analyzing large scale complex networks because of the high algorithm complexity.By analyzing the local structural features of neteorks,it is found that if the frequency of a node appearing on the shortest paths between its neighbor nodes is higher,the structural gap feature between its neighbor nodes is more obvious,which means that the target node is of higher bridging effect and more important in structure.Therefore,this paper proposes a node importance ranking algorithm based on node bridging features in complex networks.The algorithm effect is evaluated by the maximal connectivity coefficient and the network efficiency after removing nodes statically or dynamically in in six open real network datasets and a synthetic small world network.The experimental results show the proposed algorithm is more excellent in evaluating node importance than the degree index,K-shell index,LLS index based on neighborhood similarity and WL index based on degree information of the node and its neighbors.Especially in the initial stage of network attacks,the advantages of the proposed algorithm are more obvious.A complex network node importance mining algorithm based on information entropy is designed.The information entropy used in this paper is a kind of structure entropy.In complex networks,structure entropy refers to the evaluation and measurement of the complexity of network structure from the topological characteristics of network structure.The most important part of the entropy construction process is the set of probabilities needed to construct the entropy.In most cases,the degree information is used to build the entropy.In this paper,the network structure entropy of a node is defined by the betweenness and information entropy of the Ego network.The calculation of the node betweenness of the self-network only needs to obtain one piece of network information of the node,so that the algorithm is of low complexity and can be used for large-scale networks.This paper comprehensively considers the weights of network nodes and their neighborhood nodes and proposes the mapping entropy of betweenness of Ego network.The simulation experiments in multiple real networks show that the proposed algorithm can achieve higher accuracy in node importance identification than the degree index and the structure entropy algorithm derived from the degree index.A key edge evaluation algorithm based on path and complete graph is proposed.In a complex network,sometimes it is not possible to block all external connections of the node,but it is necessary to cut off the most important edges,where the key edges of the network need to be determined.Taking the path in the network as the starting point,combining the degree and betweeness of edges,and considering the complete graph,a new high-precision edge importance mining algorithm is proposed in this paper.Simulation experiments are carried out on 14 classical reral network datasets and two synthetic network,the ER network and LFR network.The ranking accuracy of the algorithm is evaluated by the maximal connectivity coefficient and network efficiency.Compared with the algorithm of Jaccard coefficient,degree product of edge endpoints,and betweenness product of edge endpoints,the algorithm proposed in this paper can mining the importance of edges more accurately.A complex network influence maximization algorithm based on coreness number and H-index is proposed.To solve the problem of low computation efficiency and unextensibility of the Greedy algorithms in large-scale complex networks,a heuristic algorithm based on level features of coreness and spread features of H-index is designed in this paper.The process of this algorithm is to calculate the coreness and H-index of all nodes in the network firstly,and secondly calculate the most influential node at this time considering both the two properties and take it as the initial node,and then calculate the influence range of the current node through the constraint condition of coreness and Hindex,and finally find the next node through covering algorithm.Through this algorithm,it can be ensured that the found initial nodes have the highest influence,and the overlapping area of the influence of initial nodes is smaller,thereby maximizing the influence.The experimental results in five real network datasets,as well as BA network and LFR network,show that compared with the algorithms of degree index,coreness number,H index and discount,the proposed algorithm has higher accuracy of initial nodes sets identification with a wider range of propagation rates.