The Study Of Evolving Models And Key Techniques For Online Social Networks

With the rapid development of various online social networks, nodes of social network research scale up to millions or even hundreds of millions. Online social networks have large scales, many links, complicated relationships and so on. Evolution of network structure is characterized by two important aspects of online social network research, and further expanded into three issues such as evolving models, important user recognition and link prediction. The essence of evolving networks models research is to study the mechanism of network generating, including the relationship of the network’s components and overall characteristics of the network, which is a macroscopic overall research from the part of network. Centrality and user behavior are two important indicators which depict the evolution of network. Centrality is an important factor which can affect the evolution of social networks, and it is also one of the key indicators to measure the importance of one user. The user behavior is another key indicators to measure the importance of one user, and it is also one of the conditions which the link prediction dependents on. On this basis, the evolution of network, the important user recognition and link prediction form an organic whole. In this paper, in-depth research on these three issues has been involved and a series of models and algorithms have been proposed. Innovations and achievements of this paper are as follows.Network evolution.(1) To deal with the issue that the existing network evolution models can not accurately portray the issue that old users pay attention to new users when the online social networks are accelerated growth, we present p-growing network model by copying, accelerated growth network model by copying and renewal and accelerated growth network model by copying in turn. Theoretical analysis, numerical evaluation and measurement in real network show that the topological characteristics of these models are the same as the real online social networks’, which can depict the evolution of real network precisely.(2) To deal with the issue that the lack of mathematical methods for characterizing network topology currently, we present analytic methods of the degree distribution, the average shortest path length and clustering coefficient of these three network evolution models previously proposed. Given the law of topological features growth, it also provides a reference for the theoretical analysis with accelerated growth network models.Topological characteristics.(3) To deal with the issue that the important user recognition algorithm can’t sort users by importance precisely in online social networks, we present an important user recognition algorithm based on relationships of users which considers the dynamic relationship between users ’mention’ and its frequency by an iterative way to quantify the importance of users. The convergence and time complexity of algorithm have been analyzed and compared with mainstream algorithms, the problems such as zombie deception can be avoided, and it is better able to identify the important users in online social networks.(4) In our work, we also work on the link prediction problem in online social network. The link prediction problem can be formulated as a binary classification problem, and can be handled using the machine learning algorithm. A sparse classification algorithm called User Behavior Kernel Projection Machine is proposed. It is a novel way to realize sparse empirical feature-based learning different from the regularized kernel projection machines. Some theoretical theorems are also proposed and analyzed in our work. Experimental results show that the algorithm outperformed the previous algorithm in several key indices with smaller test errors and more stability.