Figure Symmetric Theory In Social Network Analysis Applications In A Number Of Important Issues

Social network can be used to model entities and their relationships in the society. Recently, social network analysis has attracted more and more researchers since many real application problems could be solved based on social network modeling, such as information processing, distributed search, and diffusion of message. The surge of social network analysis also makes graph (network) data management become one of the hottest research topic within the database and data mining community.This dissertation gives a study to several important problems in social net-work analysis, based on graph symmetry theory. Graph symmetry theory de-scribes the equivalence relationship on topological structure between graph objects (vertices and edges). This equivalence relationship characterizes the inherent in-variance existing in network structure. Latest results in complex network research shows that, real networks (including social networks) are very symmetric. The major contribution of this dissertation is that it first applies network symme-try, which is a ubiquitous property of real networks, to solve real social network analysis (especially social network data management) problems.Specifically, this dissertation mainly focuses on the problems of identity anonymization, shortest path query, and community detection in social networks. For identity anonymization problem, we proposedκ-symmetry model, which could resist attacks based on any structural knowledge, and we also carefully examined the utility of the anonymized network; For shortest path query problem, we pro-posed lossless algorithms to compress the index structure of shortest paths, which dramatically reduces the storage cost; And for community detection problem, we proposed a novel algorithm by utilizing the tie strength information, based on the inherent relationship between local symmetry and weak-tie phenomenon within social networks. This dissertation also briefly discusses the application of graph symmetry theory on other important topics in social network analysis, includ-ing characterization of vertex importance, network robustness, network evolution, and substructure pattern enumeration.