Research On Node Importance Evaluation And Community Discovery In Social Networks

Evaluate nodes importance and discover communities are both classic problems in the research of social network. With the development of internet of thins, interpersonal networks, socialization business, etc., the social informatization is further extend, and the research of social network faces new challenges, particularly social network model and analysis considering the characteristics of multi-social relations, multi-property, and dynamic overlapping,etc., but most traditional approaches of social network analysis cannot deal with it. Aiming at these problems above, hypergraph theory has been introduced into research of social nework to model social network, based on it, this paper not only proposes a node importance evaluation approach based on data field model, but also put forward a hierarchical clustering method for detecting overlapping community structure based on multi-social relations, these research provide a new approach for evaluating node importance and discovering community in social network.This paper contains these works listed below.1. The hypergraph model of social network is proposed.According to traditional graph model is indadequate for representing real social network—articularly with regard to the characteristics of multi-social relations, multi-property, and dynamic,etc.. Based on the hypergraph theory, we use nodes denote actors, and hyper-edges denote relationships between actors to build the hypergraph model of social network, in this model, nodes and hyper-edges properties and network topology are combined, and the network's dynamic can be decribed. Moreover, we take two real-world networks for example to show the process and advantage of this method.This model afforded supports for later studies on the node importance evalution and community discovery.2. The network potential model and node importance evaluation method based on data field theory are proposed.The data field theory is introduced to the hypergraph model of social network, by regarding nodes'multi-property characteristic, we build the data field model based on three main factor: node mass, radiation radius and influence factor. Its main process includes computing node mass by using projection method, computing radiation radius by using extended Floyd algorithm to find shortest paths between all pairs of nodes in a hypergraph, and computing influence factor through minimizing potential entropy. Moreover, by defining and computing the node potential and network potential, we propose an approach of Network Potential Decrease Rate(NPDR) based on data field for evaluating node importance. The theory and experimental results on terrorist organization network and davis southern club women network verify its efficiency and feasibility. 3. A Hierarchical Clustering method based on Hyper-edge (HCH) is proposed to discover community in social network.In contrast to the existing literature, which has entirely focused on grouping nodes, in this paper, on the basis of the hypergraph model of social network, a hierarchical clustering method based on hyper-edge is proposed, its main process includes defining and computing similarity between the hyper-edges, megering the hyper-edges, defining and computing partition density to measure the quality of a hyper-edge partion. Then, we propose a approach of discard-relink to deal with"Overlap Effect"caused by big hyper-edge. Finally, the analysis and experimental results show that the HCH method not noly can effectively discover the community but also can detect overlap.