Research On Structure, Evolution And Apllication Of Online Social Networks

With the development of computer science and Internet technology,online social networks,represented by social networking,information sharing and online shopping have been flourishing and becoming an indispensable part of our social and economic activities.Due to the values it contains in terms of social economy and networking attributes,socialized network has gradually drawn the attentions of the researches in network mining and brought about numerous research findings.Those findings concentrate on three main aspects,which are network analysis,evolutions and applications.Specifically,network analysis is mainly based on empirical network topological analysis and community mining.Researches on network evolution concentrate on network evolution modeling,linking mechanism and network growth.The researches on network application cover lots of fields,including two typical research directions,which are information recommendation and network prediction.Based on users' past behaviors,recommendation aims at predicting users' potential choices in the future.However,network prediction,represented by linking prediction,aims at mining the potential links through learning the existing network structure.Although there have been a lot of profound researches about social networks,some shortages still exist.Firstly,most established studies struggle to find a good graph clustering by minimizing similarities of vertices between clusters for community division.However,the topological similarities of vertices in each cluster are considered only little,which leads to worse clustering results.Secondly,traditional network evolution models just consider the topological linking mechanisms and neglect the nodes' attributes,which results in some unreasonable predicted links.Thirdly,there exit abundant recommendation algorithms,but most of them still have defects,such as ignoring the evolution attributes of bipartite networks,the similarity depending on degrees of users or items,failing to solving the cold-start problem,inadequate mining rating behaviors and so on.At last,most of the researches on linking prediction have focused on global prediction and paid no attention on personalized linking prediction,which leads to fail to solve the problem of friend recommendation in social networks.Target at those shortcomings above,in this paper,we have introduced a new graph clustering algorithm (8 from a new density point of view based on analysis about empirical networks.Then,we have proposed the gravity network evolution model by considering the attributes of nodes.Subsequently,we have improved the recommendation algorithms in four aspects: network evolution mechanism,similarity algorithms,cold-start problems and rating behaviors mining.Lastly,we have solved the problems in personalized linking prediction and macro economic prediction based on network structure and evolution.Specifically,the main works and innovative points of this paper are as follow:(1)Graph clustering based with density-cut.In this paper,we find a good graph clustering by minimizing similarities of vertices not only between clusters but also in clusters for community division.We have introduced a novel graph clustering algorithm,(8.Our extensive experiments on synthetic data and real world data demonstrate that(8 has many desirable properties such as accurate clustering results and low time cost.Moreover,(8 outperforms several mainstream clustering methods.(2)Gravity evolution model.In this paper,we have proposed gravity network model,which both take into account preferential attachment and nodes' attributes.Compared with ER model and scale-free model,the experiment results on real networks demonstrate that the artificial networks generated by our model are more close to the real networks in many topological indices.(3)Improvements of recommendation algorithms.Firstly,we generalize the gravity mechanism to recommendation for its great effects in network evolution.The similarity is computed based on the popularity and attributes of items and has good performance.Secondly,we propose a novel similarity index named CosRA.By applying the CosRA index to real recommender systems,we show that the CosRA-based method has better performance than the state-of-the-art methods.Thirdly,We convert the cold-start problem into a clear mathematical model.We then propose a degree-based solution.Finally,by in-depth mining users' rating behaviors and introducing rating entropy,the classical rating-similarity algorithm is optimized and improved forecasting accuracy.(4)Personalized linking prediction.To solve the problem of friend recommendation in social networks,we introduce the concept of personalized linking prediction,which changes the pattern of global linking prediction and recommends equal number of friends to each user.We add the ground node to improve heat conduction.Then,we propose a novel linking prediction algorithm,which combines local random walk with ground heat conduction,and the results showed that this method has better performance in many indices.We have found an effective solution to personalized linking prediction.(5)Macro economic prediction based on online social activities.As traditional computing economic indices unusually based on the economic census with a series time delay,we have analyzed more than 100 million users' activities and explored latent relationships between the online social activities and local economic status.Then,we have proposed a novel method to utilize online social networks to predict the micro economic structure.