Community detection has a very important role in data processing and analysis, which is very hot in recent years. However, traditional algorithms have shortcomings in both time complexity and precision. In this paper,...
详细信息
ISBN:
(纸本)9781509033782
Community detection has a very important role in data processing and analysis, which is very hot in recent years. However, traditional algorithms have shortcomings in both time complexity and precision. In this paper, we introduce a Modified Genetic Algorithm (MGA) that with alleles encoding and half uniform crossover to detect community structure. In the algorithm, each allele of the chromosome stands for the community index of the corresponding node. At the same time, half uniform crossover can better prevent the elite individuals from destroying. And we choose modularity function as its fitness function. It does not need to know how many communities the network has. In order to identify our algorithm is effective. We use both artificial random network and real networks to test our algorithm. The experimental results show that the MGA algorithm can be applied to community detection, and its accuracy and time complexity can reach the effect of classical algorithms.
In this paper, we propose a weighted modularity Q(w) based on the similarity of weights on edges and a threshold coefficient zeta to evaluate the equivalence of edge weights. Simulations on benchmark networks and real...
详细信息
In this paper, we propose a weighted modularity Q(w) based on the similarity of weights on edges and a threshold coefficient zeta to evaluate the equivalence of edge weights. Simulations on benchmark networks and real networks show that optimization on the modularity enable us to obtain groups of nodes within which the edge weights are distributed uniformly but at random between them. The communities can reveal the uniform connections (stable relationships measured by the similarity of weights on edges) between nodes or some similarity between nodes' functions. Furthermore, with the dynamical moving of zeta, we observe that optimization on the Q(w) allows for the discovering of a special hierarchical organization which reveals different levels of uniform connections between nodes in networks. The substructures revealed by the hierarchical organization enable us to obtain more information of networks, and give a potential way for partly remedying the intrinsic resolution problem of modularity. (C) 2013 Elsevier B.V. All rights reserved.
The key to interpreting multi-electrode recorded neuronal spike trains are the firing patterns hidden in a population of neurons. Here, we present a new firing pattern detection method based on community structure par...
详细信息
ISBN:
(纸本)9783319124360;9783319124353
The key to interpreting multi-electrode recorded neuronal spike trains are the firing patterns hidden in a population of neurons. Here, we present a new firing pattern detection method based on community structure partitioning method, in which we apply the genetic evolutionary algorithm to maximize modularity function Q. We propose a new genotype encoding method to represent the functional connections between neurons. Independent of prior ` knowledge,' this method automatically finds the number and type of firing patterns in neuronal populations, an advantage over current leading methods.
In recent 15 years, the study of complex networks has been gradually becoming an important issue. Community structure is an interesting property of complex networks. Researchers have made much exciting and important p...
详细信息
ISBN:
(纸本)9783038350125
In recent 15 years, the study of complex networks has been gradually becoming an important issue. Community structure is an interesting property of complex networks. Researchers have made much exciting and important progress in community detection methods. The paper introduced the definition and significance of community structure;elaborates on the overview of community discovery algorithms and a proposed taxonomy according to the basic principle that they used. modularity function was recommended briefly. Finally, described several popular test methods and benchmarks.
Considering the problem of overlapping community detection in directed and weighted complex networks, we proposed an overlapping community detection algorithm named MSG-OCD based on the multistep greedy strategy. The ...
详细信息
ISBN:
(纸本)9781479927913
Considering the problem of overlapping community detection in directed and weighted complex networks, we proposed an overlapping community detection algorithm named MSG-OCD based on the multistep greedy strategy. The MSG-OCD integrates the weighting mechanism into the traditional modularity function, uses the improved multistep greedy strategy to detect the initial community structure, and analyzes the overlapping community structure in accordance with the overlapping community strategy. The MSG-OCD algorithm not only has a lower time complexity but also can prevent premature condensation into few larger communities. We verify the validity of the MSG-OCD algorithm through benchmark named Enron email set, which is a directed and weighted network.
In this paper, a new model for reputation collusion detection is established based on hypergraph theory. Users of a e-commerce system may have some kind of relationship according to the corresponding application. Such...
详细信息
ISBN:
(纸本)9781479925483
In this paper, a new model for reputation collusion detection is established based on hypergraph theory. Users of a e-commerce system may have some kind of relationship according to the corresponding application. Such kind of connected users can be viewed as vertices jointed by hyperedges, and thus formed a hypergraph. Colluders are those clusters in the hypergraph that all of their vertices are closely connected via hyperedges. Thus the task of detecting colluders from common users is converted to be a problem of finding those tightly connected clusters, which can be found by splitting the hypergraph according to modularity defined in this paper. Experiment shows that such modularity attribute of colluder groups are generally of large values while are of little value for common user groups, which demonstrates the effectiveness of our proposed model and algorithm.
This study aims to tackling community detection problems in dynamic social networks. The main approach focuses on exploring the idea of random walk in formulating modularity functions for community detection. Under th...
详细信息
ISBN:
(纸本)9780769543758
This study aims to tackling community detection problems in dynamic social networks. The main approach focuses on exploring the idea of random walk in formulating modularity functions for community detection. Under this approach, a modularity function is defined as the difference between the probability of a Markov chain induced by a community and the probability of a null model that assumes no detectable community structure exists in the network. In this paper, we demonstrate the modularity-based approach by applying it to identify group boundaries in an adolescence friendship networks spanning a period of five months. Results and future directions will be discussed.
Community structure has been recognized as an important statistical feature of networked systems over the past decade. A lot of work has been done to discover isolated communities from a network, and the focus was on ...
详细信息
Community structure has been recognized as an important statistical feature of networked systems over the past decade. A lot of work has been done to discover isolated communities from a network, and the focus was on developing of algorithms with high quality and good performance. However, there is less work done on the discovery of overlapping community structure, even though it could better capture the nature of network in some real-world applications. For example, people are always provided with varying characteristics and interests, and are able to join very different communities in their social network. In this context, we present a novel overlapping community structures detecting algorithm which first finds the seed sets by the spectral partition and then extends them with a special random walks technique. At every expansion step, the modularity function Q is chosen to measure the expansion structures. The function has become one of the popular standards in community detecting and is defined in Newman and Girvan (Phys. Rev. 69:026113, 2004). We also give a theoretic analysis to the whole expansion process and prove that our algorithm gets the best community structures greedily. Extensive experiments are conducted in real-world networks with various sizes. The results show that overlapping is important to find the complete community structures and our method outperforms the C-means in quality.
暂无评论