Mining Community Structures From Complex Networks Using Distance-Based Similarity

The Small-world and Scale-free properties make the complex networks describing the various systems in real-world more accurately, such as social system, biological system, scientific system etc. The study of complex networks has attracted many researchers from different fields of mathematics, physics, sociology, biology and computer science. Then, complex networks have become one of the most important areas of multidisciplinary research.Paralleling with the statistical properties of Small-world and Scale-free, network community structure is another fundamental and important topological properties of complex networks, within which the links between nodes are very dense, but between which they are quite sparse. To mine community structures from the in real-world complex networks is the foundation for both theoretical research and practical applications, so it became a hot problem in data mining domain.Firstly, this paper discusses three main points of the complex networks, the research background, the current and future significance and the present status. Then, the paper focus on some representative algorithm about complex networks recognition, such as K-L algorithm, GN algorithm, HITS algorithm, FEC algorithm etc.Although there exists many works with regard to community mining, few of them studied the connections between the local distance among nodes and the global community structures of networks. In this work, we have researched this issue and found that the nodes with nearer (or further) distance tend to belong to the same (or distinct) community with bigger probabilities, meanwhile the distance among nodes within the same (or distinct) communities tend to be smaller (or larger). Based on the heuristic in terms of the link between distance and community structure, we describe a distance-based similarity measure as well as a novel community mining algorithm DSA, which is a divisive algorithms of hierarchical clustering. Complex networks can transform as a hierarchical tree of community structure. We have validated the DSA against four benchmark networks, random networks with known community structure, Karate network, Dolphin network and Football network. Through rigorous testing, the experimental results have shown that the DSA is able to accurately discover the potential communities with their hierarchical structures from the tested benchmark networks. Comparing with some classical clustering algorithms, the DSA has more precision in result.After discovering the communities, we need to identify the meaning of them or they'll be meaningless. The nodes in communities are identified orderly after using the DSA. The order is closely linked with the degree of nodes' contribution to the communities' meaning. And node is identified earlier (later), the properties of the nodes' contribution to the community is greater (smaller). Based on the feature introduced above, we describe a new concept, accept-probability. In addition, a novel recognition algorithm to communities' meaning-MEA is introduced, and the MEA can complement and strengthen the DSA. By Football network and Word Association network, we validate the MEA through rigorous testing. The experimental results have shown that the MEA is able to discover the meaning of communities perfectly.