Research On Community Mining In Complex Networks

Many complex systems in the real world exist in the form of networks, such as socialnetworks, biological networks, Web networks, etc, which are collectively referred to ascomplex networks. The area of complex networks has attracted many researchers fromdifferent fields such as physics, mathematics, computer science, etc. While a considerablebody of work addressed basic statistical properties of complex networks, such as the existenceof "small world effect" and the presence of "power laws" in the link distribution, anotherproperty has also been paid particular attention, that is,"community structure": the nodes innetworks are often found to cluster into tightly-knit groups with a high density ofwithin-group edges and a lower density of between-group edges. The community miningproblem, which this paper refers to, is to discovery and interpret community structures fromvarious complex network data.The ability to detect community structure has a large amount of usefulness in manyaspects. For example, nodes belonging to the same community may have much more commonfeatures than those in different communities, which could be used to simplify the functionalanalysis of complex networks. Furthermore, community structure may provide insights inunderstanding some uncharacteristic properties of a complex network system. For instance, inthe world wide web, community analysis has uncovered thematic clusters; in biochemical orneural networks, communities may be functional groups and separating the network into suchgroups could simplify functional analysis considerably.In this work, we focus on discovering communities from complex networks, and offerseveral community mining algorithms based on ant colony optimization, genetic algorithmand Markov dynamics, which are introduced as follows.(1) For detecting communities, a new ant colony optimization strategy building on theMarkov random walks theory, which is named as RWACO, is proposed here. The frameworkof ant colony optimization is taken as the basic framework in this algorithm. In each iteration,a Markov random walk model is employed as heuristic rule; all of the ants' local solutions areaggregated to a global one through an idea of clustering ensemble, which then will be used toupdate a pheromone matrix. The strategy relies on the progressive strengthening ofwithin-community links and the weakening of between-community links. Gradually thisconverges to a solution where the underlying community structure of the complex networkwill become clearly visible. The proposed RWACO has been evaluated on several real-worldnetworks, and compared with some present competing algorithms. Experimental result hasshown that RWACO is highly effective for discovering known communities. (2) Aiming community mining problem, a local search based genetic algorithm (GALS)which employs a graph-based representation (LAR) has been proposed here. The core ofGALS is a local search based mutation technique. In order to overcome the drawbacks of theexisting mutation methods, a concept namely marginal gene is firstly proposed, and then thelocal monotonicity of modularity function Q is deduced from each node's local view. Basedon these two points, an effective as well as efficient mutation method which is combined witha local search strategy has been given at last. Moreover, in this paper the percolation theory onER random graphs is employed to further clarify the effectiveness of LAR presentation; aMarkov random walk based method is adopted to produce the accurate and diverse initialpopulation; the solution space of GALS will be significantly reduced by using a type of safemechanism. The proposed GALS has been evaluated both on synthetic benchmarks and onsome real-world networks, and compared with some present competing algorithms.Experimental result has shown that GALS is highly effective and efficient for discoveringcommunity structure.(3) For discovering overlapping communities, we propose a Markov dynamics basedalgorithm, called UEOC, which means,"unfold and extract overlapping communities". InUEOC, when identifying each natural community that overlaps, a Markov random walkmethod combined with a constraint strategy, which is based on the corresponding annealednetwork (degree conserving random network), is performed to unfold the community. Then, acutoff criterion with the aid of a local community function, called conductance, which can bethought of as the ratio between the number of edges inside the community and those leaving it,is presented to extract this emerged community from the entire network. The UEOC algorithmdepends on only one parameter whose value can be easily set, and it requires no priorknowledge on the hidden community structures. The proposed UEOC has been evaluated bothon synthetic benchmarks and on some real-world networks, and was compared with a set ofcompeting algorithms. Experimental result has shown that UEOC is highly effective andefficient for discovering overlapping communities.The study result of this thesis, especially of (overlapping) community mining based onintelligent algorithms and Markov Dynamics model, are of both theoretical and practicalbenefit to further researches on complex network analysis.