Social Networks: Topological Properties And Algebraic Properties

Modern research on social networks discover lots important results on real-world networks and small-world models by numerical experiments, simulations and heuristic analysis. The most important topological characters are small-world phenomenon and clustering. Small-world phenomenon means that the average distance or diameter of the network is significant smaller than the number of vertexes while clustering means that number of triangles are large enough compared with regular lattice. Watts and Strogatz first proposed their model(WS model) by rewiring edges with probability p from regular lattice and discover by numerical simulation that when p lies in some interval the model possesses small-world phenomenon and clustering. Watts and Strogatz conjectured that there exists a class of graphs with large clustering and average distance(or diameter) like random graphs and called such graph as small-world networks. A bit later Newman and Watts introduced the NW model which is the union of a regular lattice and Erdos-Renyi random graph ignoring the loops and multi-edges. The clustering coefficient of NW model is simple to calculate while Newman, Moore and Watts gave analytical result on average distance by approximation of continuous model and mean field theory(meanwhile Barbour and Reinert also provided theoretical result of average distance on continuous NW model). In this thesis, we offer analytical results to give a class of graphs called generalized small-world graph satisfying small diameter and high clustering. Applying isoperimetric constant analysis we give an upper bound on diameter and applying combinatorics method we give a lower bound on clustering coefficient of generalized small-world model, this proves that generalized small-world graph is a class of small-world networks.The algebraic properties of network is that investigate the graph in a matrix form (usually in adjacency matrix or Laplacian matrix) and study the properties of their spec-trums, such as the second smallest eigenvalue(also called algebraic connectivity) and largest eigenvalue of Laplacian matrix which are closely related to dynamic systems and has wide applications in consensus problem of multi-agent system and synchronization problem on coupled system. Olfati-Saber discovered the algebraic connectivity of WS model is much larger than that of regular lattice, which is important to improve consensus speed in multi-agent consensus problem. This paper includes the estimation of algebraic connectivity of NW model and lower bounds of algebraic connectivity gain on NW model which can show the consensus is ultrafast on small-world network and help to design a multi-agent consensus system with few connection and ultrafast consensus speed. We also give sufficient conditions for consensus small-world topologies with respect to time delays, the robustness to time delay of small-world networks. With respect to the synchroniza-tion problem, we prove the synchronizability increment in the small-world networks and determine the class of the small-world networks which is Barahona-Pecora synchronizable.The local topology like community structure is also very important for social net-works. Although there are lots of different approaches to find communities, there still lack of universal effective fast algorithm for community detection which can determine the number of clusters as well as the partition. This thesis introduce a method called weak nodal domain partition(WNDP) which projects the elements of single eigenvector or pairs of several eigenvectors of Laplacian matrix onto one dimensional or higher di-mensional Euclidean space, and first partite vertexes with respect the origin point or axis, then find the components in original network of each part of vertexes. We also introduce three parameters to compare results between WNDPs of different eigenvectors or pairs of eigenvectors, and in general this is a fast algorithm and can determine the number of clusters.