Research On Key Technologies Of Analyzing And Mining Social Networks

A social network is a social structure made up of individuals which are tied by so-cial links. In recent years, with the rapid development of information technology, onlinesocial networking services and micro blogging service received a lot of attentions. So-cial networks provide people a comprehensive communication platform of interaction,knowledge sharing, information dissemination, and so on. It also brought a significantimpact on people's daily life and behaviors. Therefore, at this age of online social, weconsider the social network has important theoretical and practical value on research andapplications.Analyzing and mining the online social network also brings great challenges. Differ-ent with traditional information networks, social networks have their unique characteris-tics. For example, individuals and groups in a social network reflect strong social charac-teristics in behavior, and show strong interdependence with the other nodes and networkcontext; Diverse online social network applications bring various network attributes, andthe description of individuals or groups are multidimensional; The individuals and thenetwork topology structure interact continuously, and the content and structure are corre-lated; The individuals publish new contents on the network, form new connections, andthe social networks are evolving over time. In this dissertation, social, multi-dimensional,correlationandevolutionarefourimportantfeatures,andweconductedthecorrespondingresearch on these four features. The content and contributions include:(1) On analyzing the sociability of individuals, we study the interdependence andsupportiveness among vertices. We extract the relationship of interdependence from or-dinary social connections, and propose a way for measuring it. We study the relationbetween topological structure and individuals'social impact, and propose a formal def-inition of interdependence, so that a social network can be converted to an independencenetwork. We also develop an efficient algorithm for calculating the individuals'support-iveness, which mimics a voting process. The individuals'supportiveness can be adoptedfor ranking social entities. Different with other ordinary scoring functions, our support-iveness measure reflects the individuals'contribution to others and one's reliability.Our interdependence model can also be used for discovering the tightly self-dependedand connected cliques. We also propose the corresponding definition and measures.(2) On the multidimensional context, we focus on discovering the communities withmulti-constraints. In social networks, community size and tightness are often two con-flicting goals. In this paper, based on the weighted graphs, in order to detect the large and tightly connected subgraphs, we introduce a novel community model based on nearestneighbors and quasi-cliques. We analyze the constraints between the attributes of tight-ness and community size, and introduce a mining algorithm based on the constraints. Ourmethod can detect the communities on different subpart of a large graph, and the resultscan meet the requirement of both goals. We analyze and utilize the impact from multipleconstraints, and develop efficient searching algorithms and pruning techiques.(3) For the correlation of user generated content and topological structure, we focuson extracting the featured vertex cluster in a multi-hierarchical way. In order to analyzethe relevance between clustered vertices and their rich label information, in this paper,a hierarchical structure extraction approach based on agglomerative clustering has beenproposed, and a density estimation based on topological structure has been designed. Byconducting the hierarchical aggregation on layers of hierarchical structure, the charac-teristic of clusters can be measured. We design efficient algorithms for estimating theparticularity score. By conducting the pruning in a bottom-up way, the featured clusterscan be calculated precisely.(4) The social networks are evolving over time. We focus on studying the predictionproblemoftopics'socialimpacttrends. Inthispaper, weconsiderboththestructuresim-ilarityandtopicalpropertyofsocialnetworks,andanoveltimeseriesmodelisintroduced.The existing user-generated contents can be summarized with a set of valued sequences.Moreover, we introduce a novel hybrid similarity measure, and a best matching basedsupervised learning process are conducted for training the time series. The events beforethe current timestamp can be adopted as a training set, and an early predictor will be gen-erated by learning the rules from the training set. The newly coming events will be usedfor verifying the predictor, or assessing and tuning it.In summary, in this paper, we aim at the four key characteristics of social networks.Some key techniques, including entity ranking, community discovery, feature extractionand trend prediction, are studied. These techniques are interesting and useful, and havebrilliant perspective on social network analysis and data mining.