| With the rapid development of computer and Internet,the scale of social networks and computer networks is increasing dramatically,and adding edges(links)to existing networks are somewhat inevitable.Therefore,link addition strategy has become an important research topic in the process of dynamic evolution of networks.Link-addition strategy mainly studies the optimal design of network according to different optimization objectives.In the era of big data,with the increase of network size and structure complexity,the research methods and conclusions based on network structure can not meet the needs of practical applications.Therefore,it is necessary to design link-addition algorithm with a variety of related theories of network.This thesis analyses the relationship between Fiedler vector and graph structure,studies the structural properties of networks from the algebraic point of view,and proposes a fast and effective link-addition algorithm to maximize algebraic connectivity and transmission capacity.In addition,a link-addition algorithm to minimize the average shortest path of networks is proposed based on the structural hole theory in social sciences.The purpose of this thesis is to provide an efficient and feasible Edge-Adding algorithm for large-scale network expansion,and to provide ideas for studying network structure from multiple perspectives.Generally speaking,the contributions of this thesis are four-fold.1.In this thesis,we further study the relationship between Fiedler vector and graph structure.Fiedler vector is corresponding to the second smallest eigenvalue of Laplacian matrix of a graph.It is widely used in graph segmentation,data clustering,social network and other fields.The significance of Fiedler vector lies in its connection between the algebraic features of a graph(such as eigenvalues and eigenvectors of Laplacian matrix)and the topological structure of a graph(such as the connectivity of a graph).We can study the structure of graphs by the eigenvector components,positive and negative.For example,the induced subgraphs of vertices corresponding to the non-negative values of Fiedler vector components are connected.Therefore,Fiedler vectors are often used in network structural analysis.The specific research results of this paper are as follows:Firstly,this paper defines -matching graph,whose minimum degree vertex corresponds to the maximum value of Fiedler vector.And we prove that the tree graph is a -matching graph.Further sampling experiments show that most of the graphs are-matching.Then,the definition of Fiedler-Breadth-First graph is given.The characteristic of this kind of graph is that if the roots of the vertices corresponding to the maximum value of the Fiedler vector are used to generate the breadth-first graph,the minimum value of the Fiedler vector must be at the highest level of the graph.In order to verify the existence of this class of graphs,this paper finds and proves a class of such graphs.Sampling experiments also show that most of the graphs are Fiedler-Breadth-First graphs.2.Based on the relationship between Fiedler vector and graph structure,an algorithm for maximizing algebraic connectivity is designed.Algebraic connectivity is the second smallest eigenvalue of the Laplacian matrix,and it is the basic performance index of multi-agent and other network systems.This paper discusses how to increase the connectivity and robustness of networks by maximizing algebraic connectivity.At present,the existing effective algebraic connectivity maximization algorithms need to calculate it directly,which results in high time complexity and is difficult to apply in large-scale realworld networks.Based on the analysis of Fiedler vector,a heuristic algorithm,Minimum Degree and Maximum Distance(MDMD),which does not need to calculate algebraic connectivity is proposed in this paper.The algorithm is tested in large random networks and real autonomous system(AS)peer-to-peer information networks.The simulation results show that the algorithm is effective and has shorter running time than other algorithms.Therefore,it can be applied to very large networks,especially large sparse networks.3.The relationship between algebraic connectivity and transmission capacity is studied,and a link-addition algorithm for maximizing network traffic capacity is proposed.This paper studies how to improve the transmission efficiency of scale-free networks by adding edges.Based on the analysis of the correlation between algebraic connectivity and traffic capacity,an effective link-addition strategy is proposed: maximizing the incremental edge of algebraic connectivity(MACIE).Most of the existing methods are based on topological parameters,such as the path and degree of the network.MACIE algorithm studies and designs algorithms to improve transmission efficiency from the perspective of the relationship between algebraic attributes and structural parameters of the network,so it has shorter running time.The simulation results show that the MACIE algorithm is effective and its performance is superior to the previous reducing structural hole(RSH)strategy.4.Based on the theory of structural holes in sociology,an algorithm for minimizing the average shortest path length is designed.The average shortest path length is a measure of the small-world characteristics of the network,which means that the average shortest path is smaller.The dynamic evolution process of network is a small-world process,hence how to add edges to minimize the average shortest path of network has important application significance.In this paper,based on the theory of structural holes in sociology,an link-addition algorithm is designed.The core idea of this algorithm is to connect the vertices with the largest number of structural holes in the network.A large number of vertices of structural holes means that more paths pass through.Connecting such vertices can affect as many shortest paths as possible,thus it can effectively reduce the average shortest path length.The validity of our algorithm is verified by comparative experiments. |
PDF Full Text Request