Research On Algorithms For Identifying Important Node Groups In Complex Networks

Complex networks can describe complex systems in most fields such as social science,finance,and biology in the real world.A small number of nodes in a complex network have a great influence on the structure and function of the network,such as some people who are crucial to information dissemination in the Internet,or those who can accelerate the spread of infectious diseases in social networks,these nodes are called important nodes.node.The main research content of this thesis is the identification of important node groups in complex networks,that is,to identify a group of important nodes with the greatest comprehensive influence in complex networks,which is of great significance in practical applications.For example,to promote a product in a social network,first select a group of people in the network to give a free trial product,and hope that the selected people will like the new product after trying it and actively promote it in their circle of friends,so that more people will accept and buy the product,and these New users in turn promote the product further in their circle of friends.According to different research perspectives,two network types,static network and time series network,are usually used to study the identification of important node groups.The nodes and edges in the static network do not change with time,and the interaction between nodes in the sequential network follows the time sequence.Various algorithms have been proposed to identify important node groups in static networks.Greedy-based algorithms have high time complexity,especially on largescale networks,so they are not applicable;centrality measurement algorithms based on network structure,through the centrality sorting nodes,the selected nodes are easy to gather together in structure,which is beneficial to The scope of influence of other parts of the network overlaps,so that the overall influence of the node group is not large;based on the heuristic algorithm,the relationship between nodes is considered,some algorithms increase the distance between nodes,and some algorithms select nodes with local influence group,but did not effectively combine the two.Among the current algorithms for identifying important node groups in time-series networks,the snapshotbased algorithm calculates the average value of the importance metrics of nodes on all snapshots,without considering the connection between multiple snapshots and losing too much time information;Algorithms based on timing paths need to consider the interaction between nodes at each time point and other nodes,and the time complexity is too high to be suitable for real timing networks;algorithms based on eigenvectors can only obtain important node groups in a certain time layer.In general,the existing static network important node group identification algorithms are still insufficient in weakening the overlap of the influence range of node groups,and the existing time series network important node group identification algorithms are still insufficient in utilizing time information.Aiming at "the existing static network important node group identification algorithm is still insufficient in weakening the overlap of the influence range of node groups" and "the existing time series network important node group identification algorithm is still insufficient in utilizing time information",the "community-based Discovery and Local Influence Static Network Important Node Group Identification" and "Time Series Network Important Node Group Identification Based on Temporal Neighborhood Variation Centrality".The first research content of this thesis is the identification of important node groups in static networks based on community discovery and local influence.Based on the global and local structure of the network,this thesis proposes an algorithm CL that combines community discovery and local influence.Community discovery disperses the node group globally,and local influence obtains the most influential nodes within each community.This algorithm effectively solves the problem of node group The problem of overlapping influence ranges makes the comprehensive influence of selected important node groups greater.Finally,simulation experiments are carried out on 4 real static network datasets through the SIR propagation model.Compared with 9 benchmark algorithms,the results show that the proposed algorithm CL is more accurate and stable in identifying important node groups in static networks.The second research content of this thesis is the identification of important node groups in time series networks based on the centrality of time series neighborhood changes.This thesis proposes a timeseries neighborhood change centrality algorithm TNCC based on snapshots,which considers the number of neighbor nodes newly added by nodes on each snapshot.If the node’s average neighbor node change rate on all snapshots is larger,it means that it affects more nodes in the entire time interval,and its influence is greater.This algorithm utilizes the time information between different snapshots,and effectively measures the influence of nodes in the entire time period in the sequential network.Finally,simulation experiments were carried out on six real time series network data sets through the time series SIR model.Compared with seven benchmark algorithms,the results show that the proposed algorithm TNCC has a better effect on identifying important node groups in time series networks.