Research On Visualization Problems And Algorithms For Large Scale Social Network

In the era of Web 2.0, with the emergence and rapid proliferation of online social networks such as Facebook, Twitter, We Chat, Sina Microblog and so on, there is an explosive growth of the amount of users or actors in these networks. The intricate relationships among these actors make it urgent to develop large scale social network visualization techniques. To mining the characterics of large scale, rich semantics and complex community structure, we should develop specific social network visualization methods. This dissertation focuses on those problems caused by new characterics of social networks and proposes five large scale social network visualization methods.The main contributions of this dissertation are as follows:? Two algorithms, social network sampling algorithm using topologically divided stratums(SS) and social network sampling algorithm based on temperature conduction model(TCS), are proposed for sampling large scale social networks. SS divides the social network into some subnetworks according to the diameter of the network and then samples in every subnetwork. TCS starts at burning one vertex in the network and simulates the process of temperature conduction to burn(sample) vertices. These two algorithms can maintain well the topological similarity between the sampled network and original network. We evaluate our algorithms on several well-known data sets. The experimental results show that our algorithms outperform previous methods.? A visualization method, OpinionRings, is designed for visualizing and predicting the opinion distributions among different groups of actors in opinion networks.More specifically, the Opinion Rings method leverages three concentric rings with various colors to summarize the opinions of positive, negative and neutral opinion holders. In addition, it is underpinned by a collective classification algorithm to predict and visualize the opinion inclinations of neutral opinion holders according to their similarities with positive and negative opinion holders. Through quantitative objective evaluations, it is shown that the Opinion Rings method outperforms the classical force-directed visualization method and the fast multiscale visualization method in terms of the qualities of graphical layouts. Moreover, user-based evaluations confirm that the graphical layout generated by the Opinion Rings method is perceived with a higher informativeness and predictive power than that produced by two comparative methods. As a whole, our usability study reveals that both expert and novice users are satisfied with the features and the visualization outputs provided by the Opinion Rings system.? We design and develop a computational method named Multi-opinion Ring for visualizing and predicting multiple opinion inclinations among different groups of actors in online social media by extending the Opinion Rings method. The Multi-opinion Ring algorithm adheres to sound aesthetic principles such that users find it easy to directly observe and analyze the predicted opinion distributions among actors. Through controlled experiments and case studies, it is shown that the Multi-opinion Ring method outperforms the classical force-directed opinion visualization method and the fast multiscale visualization method in terms of the qualities of graphical layouts. Moreover, user-based evaluations confirm that the graphical layout generated by the Multi-opinion Ring method is perceived with a higher informativeness and predictive power than that produced by the traditional methods.? We develop an area-adaptive multi-level layout method for visualizing social networks. This area-adaptive layout can visualize social networks according to the display area and the community structure of network, so it can utilize the display area reasonably and enhance the community feature of social network. The whole process consists of two parts: multi-layered compression and top-down multi-level layout. The multi-layered compression procedure groups vertices to form clusters and then abstract the clusters as new vertices to define a new graph. This procedure is repeated until the graph size falls below certain threshold. Based on the compressed graph, we optimize the display area to top-down position all vertices.We have evaluated our layout on several well-known data sets. The experimental results show that our layout outperforms the state-of-the-art methods.In this dissertation, five algorithms are proposed to solve different problems in social networks. The SS and TCS algorithms, which are the foundation of large scale social network visualization, are used to reduce the data size of social networks. Opinon Rings and Multi-opinion Ring are designed for visualizing and predicting opinion inclinations among different groups of actors in opinion networks. Area-adaptive multi-level layout can visualize social networks according to the display area and community structure, so that it is able to utilize the display area reasonably and enhance the community feature of social network.