Detecting Circles In Ego Network Based On Entropy

Online social networks have become an important tool for people to connect with each other and obtain information.According to Dunbar's number,people can only maintain a certain number of community relations.Due to the bombing of information in social networks,the problem of information overload have arisen.By dividing the community,people and information in social networks can be screened.And the divided communities can be used as information filters.In addition,community discovery algorithms,as basic research questions in social networks,are of great significance in information dissemination models,user influence research,hot mining and personalized recommendations.Research shows that compared with the global network,the community attributes of a user-centric ego network are more obvious.Therefore,it makes more sense to research ego network.From the perspective of ego network,the integration of user text topic features and network structure features is studied in this thesis.Through the introduction of a quantitative assessment method for user text topic features and network structure features,redefine the optimization object function,and use the optimization method to detect circles in ego network.And obtaining the circles with social semantics.Improving the operation efficiency of the algorithm and accelerate the convergence of the algorithm.The following are the main research results of this thesis:1.Aiming at the problem of inaccurate circle discovery and lack of practical significance for social networks,a novel circles detection algorithm is proposed in this dissertation.The proposed algorithm defines a new object function,the detection for circles could be conducted via optimization of the function heuristically.Firstly,this thesis extracts topic distribution from user`s generated text,and introduces information entropy to evaluate user topic distribution.Then,the harmonic factor is used to combine structure function and entropy function,which leads to object function.Finally,the optimization for object function gives the solution for circle detection.2.Aiming at the problem of large-scale network circle discovery algorithm running inefficiently,the node similarity function is used to replace the network structure to optimize the object function.A circle discovery algorithm based on the graph2 vec is designed.The graph2 vec is used to obtain the graph vector of each node in ego network and define the similarity function between the nodes.An optimization object function based on graph vector is designed to complete the circle discovery process,which avoids the problem that the time complexity of the structure optimization objective function increases with the expansion of ego network scale.Improving the efficiency of the algorithm.3.In order to solve the problem of slow convergence of large-scale network circle discovery algorithms,a circle discovery algorithm that satisfies overlapping circle requirements is implemented by improving the genetic algorithm.A new chromosome coding scheme was designed.The random initialization process of the genetic algorithm is optimized.The optimal individual's local search process is added to the genetic variation process to accelerate the convergence of the algorithm.This thesis conducts an experimental verification of the algorithm for detecting circles in ego network on the real Sina Weibo dataset.Experiments show that algorithm for detecting circles in ego network based on entropy can effectively mine the topic circle that conforms to the community structure definition,also can obtain circles with obvious social semantics.The algorithm for detecting circles in ego network based on graph2 vec ensures the efficiency of the algorithm while ensuring the quality of the circle partitioning scheme.The algorithm can complete circle detection in ego network efficiently and stably.