Font Size: a A A

Community Extraction Algorithm In Complex Networks Based On Local Clustering

Posted on:2012-02-10Degree:MasterType:Thesis
Country:ChinaCandidate:L WangFull Text:PDF
GTID:2210330368488757Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
It is the abstraction of complex systems for complex networks, in which the vertices are the objects of the complex system, and the links between vertices are due to some regular pattern, natural or artificial. One of the most important features for complex networks is the community structure, which are full of information and knowledge. A community is a set of vertices in the network, densely linking to each other inside the community, meanwhile, loosely to outside.It is greatly significant to extract communities in complex networks. There are many kinds of systems that can be illustrated as complex networks, such as social networks, citation networks, the World Wide Web (WWW), biological networks. The community structure is obvious in these networks. In social networks, a community is a group of people getting together due to similar interest or identity. In WWW, a community is a set of websites focusing on the same topic, where always exists hyperlinks among these sites. It is essential for us to extract the community structure in order to understand and use these networks more effectively.Great efforts have been made to extract community structure in complex networks. However, it is infeasible for previous approaches to apply on large complex networks, as the constraint of running time and memory consumption. This paper mainly focuses on overcoming the limitation, extracting communities by local clustering. Based on local clustering, a method based on local cores is proposed:(1) Firstly, this method automatically extracts a stable local core, which is the densest part in the network. (2) Secondly, it finds out the full structure of the local community, automatically stopping as soon as no more vertices need to be added. (3) Thirdly, it can well deal with the "Outliers", by the pruning phase. Experiment results indicate that, compared with previous algorithms, this method can extract stable meaningful communities with higher quality.
Keywords/Search Tags:Complex Networks, Local Clustering, Local Cores
PDF Full Text Request
Related items