Narrow Results

This study employs five community detection methods on a rooted tree network with 600 nodes and 599 edges based on the Galo tribe’s kin naming system in Arunachal Pradesh, India. The network was originally assumed to be made up of three communities, which the algorithms were able to further divide into smaller groupings. The Louvain approach produced the most balanced distribution of community sizes, with skewness and kurtosis values close to zero, implying that the detected communities were reasonably evenly distributed in size and without major outliers. However, the Louvain algorithm found 25 communities, which is more than the network’s previously reported three communities. Further investigation may be required to integrate some of these communities in order to obtain the original known communities. Overall, this study highlights the importance of selecting an appropriate community detection algorithm for a given network and research question.

We present an application of formal concept analysis aimed at representing a meaningful structure of knowledge communities in the form of a lattice-based taxonomy. The taxonomy groups together agents (community members) who develop a set of notions. If no constraints are imposed on how it is built, a knowledge community taxonomy may become extremely complex and difficult to analyze. We consider two approaches to building a concise representation, respecting the underlying structural relationships while hiding superfluous information: a pruning strategy based on the notion of concept stability and a representational improvement based on nested line diagrams and "zooming". We illustrate the methods on two examples: a community of embryologists and a community of researchers in complex systems.

Community detection is one important problem in network theory, and many methods have been proposed for detecting community structures in the networks. Given quality functions for evaluating community structures, community detection can be considered as one kind of optimization problem, such as modularity optimization, therefore, optimization of quality functions has been one of the most popular strategies for community detection. In this paper, we introduced two kinds of local modularity functions for community detection, and the self-consistent method is introduced to optimize the local modularity for detecting communities in the networks. We analyze the behaviors of the modularity optimizations, and compare the performance of them in community detection. The results confirm the superiority of the local modularity in detecting community structures, especially on large-size and heterogeneous networks.

Community detection in complex networks is a key problem of network analysis. In this paper, a new membrane algorithm is proposed to solve the community detection in complex networks. The proposed algorithm is based on membrane systems, which consists of objects, reaction rules, and a membrane structure. Each object represents a candidate partition of a complex network, and the quality of objects is evaluated according to network modularity. The reaction rules include evolutionary rules and communication rules. Evolutionary rules are responsible for improving the quality of objects, which employ the differential evolutionary algorithm to evolve objects. Communication rules implement the information exchanged among membranes. Finally, the proposed algorithm is evaluated on synthetic, real-world networks with real partitions known and the large-scaled networks with real partitions unknown. The experimental results indicate the superior performance of the proposed algorithm in comparison with other experimental algorithms.

In order to deal with stochasticity in center node selection and instability in community detection of label propagation algorithm, this paper proposes an improved label propagation algorithm named label propagation algorithm based on community belonging degree (LPA-CBD) that employs community belonging degree to determine the number and the center of community. The general process of LPA-CBD is that the initial community is identified by the nodes with the maximum degree, and then it is optimized or expanded by community belonging degree. After getting the rough structure of network community, the remaining nodes are labeled by using label propagation algorithm. The experimental results on 10 real-world networks and three synthetic networks show that LPA-CBD achieves reasonable community number, better algorithm accuracy and higher modularity compared with other four prominent algorithms. Moreover, the proposed algorithm not only has lower algorithm complexity and higher community detection quality, but also improves the stability of the original label propagation algorithm.

Community detection offers an important way to understand the structures and functions of social network. The label propagation algorithm has attracted vast attention since it is very suitable for discovering communities from large-scale networks. However, the algorithm suffers from the instability and inefficiency problem caused by the random policies it adopted. In this paper, we propose a novel label propagation approach based on local optimization to deal with the problem. The approach introduces a pre-propagation mechanism to optimize randomly initialized labels according to special factors, for example, node compactness. After that, it traverses and relabels nodes in the descending order of aggregate influence. The experiment results demonstrate the usefulness and effectiveness of our approach.

Community detection is significative in the complex network. This paper focuses on community detection based on clustering algorithms. We tend to find out the central nodes of the communities by centrality algorithms. Firstly, we define the distance between nodes using similarity. Then, a new centrality measuring the local density of nodes is put forward. Combining the independence of the centrality, the nodes in the network can be divided into four classes. Leveraging the product of centrality and independence, the central nodes in the network are easily identified. We also find that we can distinguish bridge nodes from central nodes using centrality and independence. This research designs a community detection algorithm combining centrality and independence. Simulation results reveal that our centrality is more effective than existing centralities in measuring local density and identifying community centers. Compared with other community detection algorithms, results prove the effectiveness of our algorithm. This paper just shows one application of independence of the centrality. There may be more useful applications of it.

Identifying community structure in networks plays an important role in understanding the network structure and analyzing the network features. Many state-of-the-art algorithms have been proposed to identify the community structure in networks. In this paper, we propose a novel method based on closure extension; it performs in two steps. The first step uses the similarity closure or correlation closure to find the initial community structure. In the second step, we merge the initial communities using Modularity $Q$. The proposed method does not need any prior information such as the number or sizes of communities, and it is able to obtain the same resulting communities in multiple runs. Moreover, it is noteworthy that our method has low computational complexity because of considering only local information of network. Some real-world and synthetic graphs are used to test the performance of the proposed method. The results demonstrate that our method can detect deterministic and informative community structure in most cases.

Hierarchical analysis for network structure can point out which communities can constitute a larger group or give reasonable smaller groups within a community. Numerous methods for discovering community in networks divide networks at only one certain granularity, which does not benefit hierarchical analysis for network structure. Hierarchical clustering algorithms are the common technique that reveals the multilevel structure in the network analysis. In this work, we give a definition for scores of edges according to the basic idea of means clustering. Based on the definition, a neighbors-based divisive algorithm named neighbor-means (NM) is proposed to detect communities in networks, especially for hierarchical analysis. The divisive algorithm repeatedly removes the edge with the highest score to obtain hierarchical partitions but can recalculate the scores of edges quickly with local recalculating strategy and crucial change-rules, which makes its complexity much lower than many divisive algorithms. In addition, when the community structure is ambiguous, benefited from superiority of the defined scores, our method achieves better results than many divisive and agglomerative algorithms. Experiments with artificial and real-world networks demonstrate the superiority of neighbor-means in detecting community structure.

The community is the dominant structure that exhibits different features and multifold functions of complex networks from different levels; accordingly, multiresolution community detection is of critical importance in network science. In this paper, inspired by the ideas of the network flow, we propose an intensity-based community detection algorithm, i.e. ICDA, to detect multiresolution communities in weighted networks. First, the edge intensity is defined to quantify the relationship between each pair of connected nodes, and the vertices connected by the edges with higher intensities are denoted as core nodes, while the others are denoted as marginal nodes. Second, by applying the expansion strategy, the algorithm merges the closely connected core nodes as the initial communities and attaches marginal nodes to the nearest initial communities. To guarantee a higher internal density for the ultimate communities, the captured communities are further adjusted according to their densities. Experimental results of real and synthetic networks illustrate that our approach has higher performance and better accuracy. Meanwhile, a multiresolution investigation of some real networks shows that the algorithm can provide hierarchical details of complex networks with different thresholds.

In recent years, community detection has gradually become a hot topic in the complex network data mining field. The research of community detection is helpful not only to understand network topology structure but also to explore network hiding function. In this paper, we improve FluidC which is a novel community detection algorithm based on fluid propagation, by ameliorating the quality of seed set based on positive feedback and determining the node update order. We first summarize the shortcomings of FluidC and analyze the reasons result in these drawbacks. Then, we took some effective measures to overcome them and proposed an efficient community detection algorithm, called FluidC+. Finally, experiments on the generated network and real-world network show that our method not only greatly improves the performance of the original algorithm FluidC but also is better than many state-of-the-art algorithms, especially in the performance on real-world network with ground truth.

Community detection in networks is a very important area of research for revealing the structure and function of networks. Label propagation algorithm (LPA) has been widely used to detect communities in networks because it has the advantages of linear time complexity and is unnecessary to get prior information, such as objective function and the number of communities. However, LPA has the shortcomings of uncertainty and randomness in the label propagation process, which affects the accuracy and stability of the algorithm. In this paper, we propose a novel community detection algorithm, named NGLPA, in which labels are propagated by node gravitation defined by node importance and similarity between nodes. To select the label according to the gravitation between nodes can reduce the randomness of LPA and is consistent with reality. The proposed method is tested on several synthetic and real-world networks with comparative algorithms. The results show that NGLPA can significantly improve the quality of community detection and obtain accurate community structure.

As an important research field of social network analysis, influence maximization problem is targeted at selecting a small group of influential nodes such that the spread of influence triggered by the seed nodes will be maximum under a given propagation model. It is yet filled with challenging research topics to develop effective and efficient algorithms for the problem especially in large-scale social networks. In this paper, an adaptive discrete particle swarm optimization (ADPSO) is proposed based on network topology for influence maximization in community networks. According to the framework of ADPSO, community structures are detected by label propagation algorithm in the first stage, then dynamic encoding mechanism for particle individuals and discrete evolutionary rules for the swarm are conceived based on network community structure for the meta-heuristic optimization algorithm to identify the allocated number of influential nodes within different communities. To expand the seed nodes reasonably, a local influence preferential strategy is presented to allocate the number of candidate nodes to each community according to its marginal gain. The experimental results on six social networks demonstrate that the proposed ADPSO can achieve comparable influence spread to CELF in an efficient way.

Community structure is one of the important features of complex networks. Researchers have derived a number of algorithms for detecting communities, some of them suffer from high complexity or need some prior knowledge, such as the size of community or number of communities. For some of them, the quality of the detected community structure cannot be guaranteed, even the results of some of them are nondeterministic. In this paper, we propose a Self-Organizing Map (SOM)-based method for detecting community structure from networks. We first preprocess the network by removing some nodes and their associated edges which have little contribution to the formation of communities, then we construct the extended attribute matrix from the preprocessed network, next we embed the detecting procedure in the training of SOM on the attribute matrix to acquire the initial community structure, and finally, we handle those removed nodes by inserting each of them into the community to which its only neighbor belongs, and fine-tune the initial community structure by merging some of the initial communities to improve the quality of the final result. The performance of the proposed method is evaluated on a variety of artificial networks and real-world networks, and experimental results show that our method takes full advantage of SOM model, it can automatically determine the number of communities embedded in the network, the quality of the detected community structure is steadily promising and superior to those of other comparison algorithms.

Communities in networks expose some intrinsic properties, each of them involves some influential nodes as its cores, around which the entire community grows gradually; the more the common neighbors that exist between a pair of nodes, the larger the possibility of belonging to the same community; the more the neighbors of any one node belong to a community, the larger the possibility that node belongs to that community too. In this paper, we present a novel method, which makes full utilization of these intrinsic properties to detect communities from networks. We iteratively select the node with the largest degree from the remainder of the network as the first seed of a community, then consider its first- and second-order neighbors to identify other seeds of the community, then expand the community by attracting nodes whose large proportion of neighbors have been in the community to join. In this way, we obtain a series of communities. However, some of them might be too small to make sense. Therefore, we merge some of the initial communities into larger ones to acquire the final community structure. In the entire procedure, we try to keep nodes in every community to be consistent with the properties as possible as we can, this leads to a high-quality result. Moreover, the proposed method works with a higher efficiency, it does not need any prior knowledge about communities (such as the number or the size of communities), and does not need to optimize any objective function either. We carry out extensive experiments on both some artificial networks and some real-world networks to testify the proposed method, the experimental results demonstrate that both the efficiency and the community-structure quality of the proposed method are promising, our method outperforms the competitors significantly.

One way to understand the network function and analyze the network structure is to find the communities of the network accurately. Now, there are many works about designing algorithms for community detection. Most community detection algorithms are based on modularity optimization. However, these methods not only have disadvantages in computational complexity, but also have the problem of resolution restriction. Designing a community detection algorithm that is fast and effective remains a challenge in the field. We attempt to solve the community detection problem in a new perspective in this paper, believing that the assumption used to solve the link prediction problem is useful for the problem of community detection. By using the similarity between modules of the network, we propose a new method to extract the community structure in this paper. Our algorithm consists of three steps. First, we initialize a community partition based on the distribution of the node degree; second, we calculate the similarity between different communities, where the similarity is the index to describe the closeness of the different communities. We assume that the much closer the two different communities are, the greater the likelihood of being divided together; finally, merge the pairs of communities which has the highest similarity value as possible as we can and stop when the condition is not satisfied. Because the convergence of our algorithm is very fast in the process of merging, we find that our method has advantages both in the computational complexity and in the accuracy when compared with other six classical algorithms. Moreover, we design a new measure to describe how difficulty the network division is.

Community detection has always been one of the most important issues in network science. With the arrival of the era of big data, it is necessary to develop new accurate and fast community detection methods for the study of many real complex networks (especially large networks). Based on the concept of strong community and the analogy between the edge and the attraction, this paper proposes an effective one-dimensional “attraction” (1DA) method for community detection. The 1DA method uses the number of edges as the measure of the “attraction”. The specific 1DA algorithm is also presented using two effective ways of vertex moving (i.e. the nearest moving and the median moving). After being randomly initialized at different positions on the (one-dimensional) number axis, all vertices will move under the action of the “attraction”; eventually, the vertices of the same community will naturally gather at the same position, while the vertices of different communities will gather at different positions, thus realizing the community division naturally. This method is tested in five typical real networks and one popular benchmark, and compared with several other popular community detection methods. Theoretical analysis and numerical experiments show that the 1DA method can accurately estimate the number of communities, with low (almost linear) time complexity ($\sim O(n)$, where $n$ is the network size) and good performance in modularity and normalized mutual information in various networks (especially in the tests in large networks, the 1DA method has the best performance). The 1DA method in this paper provides a simple and practical solution to the problem of community detection.

The study of community structure is of great significance when analyzing the structural and functional characteristics of networks. Attractor is a fast community detection method with the advantage of high accuracy for complex networks. However, in the connected nodes interaction model proposed by the Attractor algorithm, there is a problem with slow convergence during the distance updating process. To solve this problem, we propose an improved Attractor algorithm based on the change trend of the distances between connected nodes. We have generally found that distances between connected nodes exhibit a consistent trend. The dynamic distance trend is determined by setting a window of evaluation. The convergence of the Attractor algorithm is accelerated by the consistent change trend. Experiments on datasets for real-world networks and synthetic networks have shown that our proposed algorithm not only maintains high-quality communities, but also reduces the calculation time significantly and greatly improves the speed of the algorithm.

In the field of community detection in complex networks, the most commonly used approach to this problem is the maximization of the benefit function known as “modularity”. In this study, it is found that the path of length two have the similar property as the edge, which is denser within communities and sparser between different communities. In order to take both edge and path of length two into consideration simultaneously, a self-loop is added to each node of the network and a novel benefit function has been defined. To divide the network into two communities, a second eigenvector method is proposed based on maximization of our new benefit function. Experimental results obtained by applying the method to karate club network and dolphin social network show the feasibility of our benefit function and the effectiveness of our algorithm.

The volatility is one of the essential characteristics of financial time series, which is vital for the knowledge acquisition from financial data. However, since the high noise and nonsteady features, the volatility identification of financial time series is still a challenging problem. In this paper, from a perspective of granule complex network, a novel approach is proposed to study this problem. First, numeric time series is structured into fuzzy information granules (FIGs), where the segments of time series in each granule would own similar volatility features. Second, by using the transfer relations among granules, granule complex network is to be constructed, which intuitively describes the transfer processes among the different volatility patterns. Third, a novel community detection algorithm is applied to divide the granule complex networks, where granules with frequent mutual transfers would belong to the same granule community. Finally, Markov chain model is carried out to analyze the higher level of transfer processes among different granule communities, which would further describe the larger-scale transitions of volatility in overall financial time series. An empirical study of the proposed system is applied in the Shanghai stock index market, where volatility patterns of financial data can be effectively acquired and the corresponding transfer processes can be analyzed by means of the granule communities.