Research On Network Community Discovery Approaches Based On Topological Potential

As the second decade of the21st century will be the social network era, many countrieshave elevated the oriented network society to a national strategic level, and the communitydiscovery is an insurmountable step in practical application of a variety of networks, soin-depth carrying out community discovery research has a very important significance.Topology potential theory is a new community discovery theory. Compared with thetraditional community discover approaches, the community discovery approach based on thetopology potential theory has many advantages. In response to the inadequacies of thetraditional community discovery approaches and the community discovery approach based ontopology potential theory, this dissertation, takes improving and development the topologypotential theory and the approach based on it as a mainline, develops the research mainlyfrom four aspects.First, the minimum point of topology potential entropy theorem has been proved.Although it is the basis and premise of the topology potential community discovery approach,the research of the existence of the minimum point of topology potential entropy onlyconfined to a few of instances. The theorem, showing that the minimum point of topologypotential entropy universally exists in all types of networks, solves the basis and theapplication scope of the topology potential theory and the approach based on it at present.Second, an overlapping node identity uncertainty measure based on topology potential isproposed. At present many community discovery approaches are hard ones that one node onlycan be belonged to one community, and lack of practical rationality. In fact, the nodes in manynetworks can be belonged to more than one community. Though the overlapping communitydiscovery approaches allow one node can be belonged to more than one community, theseapproaches lack of indicator that indicates the degree of the overlapping node belonging todifferent communities. The lacking of the indicator badly impedes the data mining andanalysis on the communities. In order to prove the validity and rationality of the measure, anoverlapping community discovery approach based on greedy strategy，a network communitynode importance-sorting algorithm and an overlapping community discovery approach basedon Pareto principle are proposed. The approach based on greedy strategy solves the problem that the connections between one community’s boundary nodes and the nodes in othercommunities are split artificially; the node importance-sorting algorithm solves the problemthat the community discovery approach often yields ambiguous results; the approach based onPareto principle overcomes the drawback of too much number of overlapping nodes in theoverlapping community discovery approach based on greedy strategy.Third, a variable scale overlapping community discovery approach based on overlappingnode identity uncertainty is put forward. The overlapping node identity uncertainty measureproposed previously is improved through the force decomposition principle. The results ofexperiments show that this approach not only has the capability of discovering variable scalecommunities but also can obtains an equivalent results of community discovery of topologypotential approach. This approach achieves controlling and custom appointing the communityscales.Fourth, a research of lossless network compression is carried out. To meet the differentneeds, two approaches of lossless network compression are proposed in this research. Oneapproach, judging importance of the nodes according to their roles playing in the communitycomposition, quantifies the importance of every node in communities, and achieves losslessnetwork compression through layers; another approach, judging importance of the nodesaccording to the distances from the community representative nodes to them, differentiates thenodes with different distances, and achieves lossless network compression throughcompression ratio. Comparative experiments show that the two approaches not only canachieve perfect compression ratio, and retain the relationship between the communities, butalso can reserve the important nodes or basic community structures during the compressionprocess according to the needs.