Search

The science of complex network theory can be usefully applied in many important fields, one of which is the finance. In these practical cases, a massive dataset can be represented as a very large network with certain attributes associated with its nodes and edges. As one of the most important components of financial market, stock market has been attracting more and more attention. In this paper, we propose a threshold model to build Chinese stock market networks and study the topological properties of these networks. To be specific, we compare the effects of different crises, namely the 2008 global crisis and the stock market disaster in 2015, on the threshold networks. Prices of the stocks belonging to the Shanghai and Shenzhen 300 index are considered for three periods: the global crisis, common period and the stock market disaster. We find the probability distribution of the cross-correlations of the stocks during the stock market disaster is fatter than that of others. Besides, the thresholds of cross-correlations are assigned to obtain the threshold networks and the power-law of degree distribution in these networks are observed in a certain range of threshold values. The networks during the stock market disaster also appear to have larger mean degree and modularity, which reveals the strong correlations among these stock prices. Our findings to some extent crosscheck the liquidity shortage reason which is believed to result in the outbreak of the stock market disaster. Moreover, we hope that this paper could give us a deeper understanding of the market’s behavior and also lead to interesting future research about the problems of modern finance theory. [ABSTRACT FROM AUTHOR]

Community detection is of considerable importance for analyzing the structure and function of complex networks. Many real-world networks may possess community structures at multiple scales, and recently, various multi-resolution methods were proposed to identify the community structures at different scales. In this paper, we present a type of multi-resolution methods by using the generalized self-loop rescaling strategy. The self-loop rescaling strategy provides one uniform ansatz for the design of multi-resolution community detection methods. Many quality functions for community detection can be unified in the framework of the self-loop rescaling. The resulting multi-resolution quality functions can be optimized directly using the existing modularity-optimization algorithms. Several derived multi-resolution methods are applied to the analysis of community structures in several synthetic and real-world networks. The results show that these methods can find the pre-defined substructures in synthetic networks and real splits observed in real-world networks. Finally, we give a discussion on the methods themselves and their relationship. We hope that the study in the paper can be helpful for the understanding of the multi-resolution methods and provide useful insight into designing new community detection methods. [ABSTRACT FROM AUTHOR]

Abstract: Community structure is an important feature in the study of complex networks. It is because nodes of the same community may have similar properties. In this paper we extend two popular community detection methods to partition online social networks. In our extended methods, the profile information of users is used for partitioning. We apply the extended methods in several sample networks of Facebook. Compared with the original methods, the community structures we obtain have higher modularity. Our results indicate that users’ profile information is consistent with the community structure of their friendship network to some extent. To the best of our knowledge, this paper is the first to discuss how profile information can be used to improve community detection in online social networks. [Copyright &y& Elsevier]

Abstract Considering that network community might have a profound effect on the cascading failure of R&D network, we generate the weighted scale-free R&D network and quantify the network community through network modularity Q. Afterwards, we propose the cascading failure model of R&D network based on SIR-CA model, and analyze the special effects on the cascading failure of R&D network through numerical simulation. The simulation results show that network modularity Q has a U-shaped effect on the robustness of R&D network, there is a negative correlation between the delay effect and the robustness of R&D network. Additionally, we verify that overlapping firms have more significant influence than those firms with the same degree and K-shell on the robustness of R&D network. This paper reveals the law of cascading failure of R&D network considering the network community, which is of practical significance to enhance the robustness of R&D network, and enrich the theory of dynamics of the network community. Highlights • The cascading failure model of R&D network based on the SIR-CA model. • The impact of community structure on the cascading failure of R&D network. • The effect of the delay effect on the cascading failure of R&D network. • The effect of overlapping firms on the cascading failure of R&D network. [ABSTRACT FROM AUTHOR]

Abstract Community detection is an important research area for its necessity in understanding the hidden structure of complex networks. A vast variety of overlapping community detection methods have been proposed in the literature, and the local expansion method is gaining much attention for its success in dealing with large networks. However, the selection of seeds limits the quality of the identified communities for the method. The paper presents a similarity-based seeding method, in which lines and triangles are searched and selected as seeds. The proposed method selects the core of a seed by the influence of the vertices, and identifies other members of the seed by a novel function, which is a combination of vertex influence and similarity. Experimental results in synthetic networks show that the proposed seeding method outperforms other seeding methods in the state of the art. Experimental results in real-world networks with ground-truth communities show that the proposed approach outperforms other state of the art overlapping community detection algorithms, in particular, it is more than two orders of magnitude faster than the existing global algorithms with competitive quality, and it obtains much more accurate community structure than the current local algorithms without any priori information. Highlights • We propose an efficient and accurate overlapping community detection method. • We propose a vertex similarity measure that takes vertex influence into account. • We propose a seeding method that selects seeds by vertex influence and similarity. [ABSTRACT FROM AUTHOR]

Abstract Community detection algorithms have important significance in the research and practical application of complex network theory. This paper proposes a community detection method by improved label propagation and fuzzy C-means. Due to low accuracy and instability detection results, we modify original label propagation framework. Primarily, initial labels of vertexes are assigned by neighbor evaluation method. Secondarily, the labels of vertexes with large diversity in each community are revised by fuzzy C-means membership vectors. Tertiarily, parameters are updated until communities status is stabilized ultimately. The results showed that this method can achieve better accuracy on synthetic and real network. Highlights • Research on complex network community detection algorithm based on improved label propagation and fuzzy C-means. • The algorithm completes initialization classification of communities by neighbor evaluation method. • The algorithm adjusts the labels of unstable vertexes by fuzzy C-means membership vectors. • The accuracy of community detection is improved on synthetic and real network. [ABSTRACT FROM AUTHOR]

Abstract Community detection is an important task with great practical significance for understanding the structure and function of complex networks in various fields. As the real world networks become larger and more complex, it is a challenge to achieve high quality of community partitioning. In order to identify community structure more effectively in complex networks, a new algorithm, which iteratively deletes edges with restrictions is proposed in this paper. The algorithm first makes use of the connection strength between vertices to divide the original network into some strongly connected communities with optimal modularity by the improved edge-deleting process, and finally reconnects the isolated vertices to initial communities for optimizing community structure. Experiments on the real-world and synthetic networks prove that the proposed algorithm achieves a competitive performance compared with other reference algorithms. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we propose two novel algorithms to detect community structure in networks based on consensus dynamics. The first algorithm identifies the communities in networks by alternating between recognizing leader nodes following the analysis of influence coefficients of nodes, and finding the nodes belonging to the groups of their corresponding leader nodes using consensus dynamics and the difference coefficients of nodes. The second algorithm is an extension to the first one via the leader-following models. After confirming the leader nodes according to the first algorithm, we reveal the memberships of nodes belonging to the corresponding leaders by performing consensus dynamics. In the second algorithm, an approach to calculating the memberships of nodes is proposed. The corresponding leader nodes of communities can be confirmed naturally and the status of nodes in networks can be determined quantitatively. Finally, our algorithms are applied to real-world and computer generated networks whose community structures are well known. The experiment results show the effectiveness and reliability of the proposed algorithms. Highlights • We seek community structure in an iterative manner without the use of modularity. • Alternating between consensus and leader selection unveils community structure. • The membership of each node is refined naturally via the dynamical evolution. • The proposed algorithms operate on real-world and synthetic networks. [ABSTRACT FROM AUTHOR]

Abstract Community detection is an important problem of complex networks analysis and various methods have been proposed to solve it. However, most of the existing methods only use the link information. As a result, the quality of their detected communities is often poor due to the sparse and noisy data existing in link information. Actually, content information of complex networks can also help to improve the quality of community detection. In this paper, we propose a method based on Multi-View Clustering via Robust Nonnegative Matrix Factorization (MVCRNMF). This method can provide a unified framework to combine link and content information for community detection. Its key idea is to build a multi-view robust NMF model with the co-regularized constraint on community indicator matrices of link view and content view. This can make link and content information complement each other during the factorization process of NMF. We devise iterative update rules as the optimization solution to the community detection model and also give the rigorous convergence proof. It is worth noting that MVCRNMF can learn the contribution weights from link and content information adaptively and this helps to save a lot of time on tuning the weight parameters. We conduct comparative experiments on four real-world complex networks. The results demonstrate that MVCRNMF performs better than state-of-the-art methods. Additionally, results of the case study on a co-authorship network also show that MVCRNMF can obtain higher quality communities. Highlights • A community detection model based on multi-view clustering is proposed. • We devise and prove iterative update rules for the community detection model. • The weight parameters of the community detection model can be learned adaptively. [ABSTRACT FROM AUTHOR]

Abstract Community structure is a very important property of complex networks, but the way to detect it remains an open problem. A new community detection algorithm based on centers and neighbors (DCN) is proposed in this paper. This method employs the idea of density peak clustering (DPC) to detect the community centers, where the clustering centers are characterized by a higher density than their neighbors and by a relatively large distance from points with higher densities. Moreover, Chebyshev inequality is adopted to select these centers automatically. To overcome the "Domino Effect" of DPC, the multi-strategy of label propagation is proposed. This strategy propagates the labels according to neighbors of the node. It is worth pointing out that the proposed method (DCN) does not need to adjust the parameters for different networks. Experimental results on both synthetic and real-world networks demonstrate the power of DCN over the comparing community detection algorithms. Highlights • Propose a uniform measure to estimate the density. • Propose the multi-strategy of label propagation to diffuse centers' labels. • The comparisons show the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Communities are ubiquitous in nature and society. Individuals that share common properties often self-organize to form communities. Avoiding the shortages of computation complexity, pre-given information and unstable results in different run, in this paper, we propose a simple and efficient method to deepen our understanding of the emergence and diversity of communities in complex systems. By introducing the rational random selection, our method reveals the hidden deterministic and normal diverse community states of community structure. To demonstrate this method, we test it with real-world systems. The results show that our method could not only detect community structure with high sensitivity and reliability, but also provide instructional information about the hidden deterministic community world and the real normal diverse community world by giving out the core-community, the real-community, the tide and the diversity. Thizs is of paramount importance in understanding, predicting, and controlling a variety of collective behaviors in complex systems. [ABSTRACT FROM AUTHOR]

Many real bipartite networks are found to be divided into two-mode communities. In this paper, we formulate a new two-mode community detection algorithm BiAttractor. It is based on distance dynamics model Attractor proposed by Shao et al. with extension from unipartite to bipartite networks. Since Jaccard coefficient of distance dynamics model is incapable to measure distances of different types of vertices in bipartite networks, our main contribution is to extend distance dynamics model from unipartite to bipartite networks using a novel measure Local Jaccard Distance (LJD). Furthermore, distances between different types of vertices are not affected by common neighbors in the original method. This new idea makes clear assumptions and yields interpretable results in linear time complexity O ( | E | ) in sparse networks, where | E | is the number of edges. Experiments on synthetic networks demonstrate it is capable to overcome resolution limit compared with existing other methods. Further research on real networks shows that this model can accurately detect interpretable community structures in a short time. [ABSTRACT FROM AUTHOR]

Clustering algorithms are attractive for the task of community detection in complex networks. DENCLUE is a representative density based clustering algorithm which has a firm mathematical basis and good clustering properties allowing for arbitrarily shaped clusters in high dimensional datasets. However, this method cannot be directly applied to community discovering due to its inability to deal with network data. Moreover, it requires a careful selection of the density parameter and the noise threshold. To solve these issues, a new community detection method is proposed in this paper. First, we use a spectral analysis technique to map the network data into a low dimensional Euclidean Space which can preserve node structural characteristics. Then, DENCLUE is applied to detect the communities in the network. A mathematical method named Sheather–Jones plug-in is chosen to select the density parameter which can describe the intrinsic clustering structure accurately. Moreover, every node on the network is meaningful so there were no noise nodes as a result the noise threshold can be ignored. We test our algorithm on both benchmark and real-life networks, and the results demonstrate the effectiveness of our algorithm over other popularity density based clustering algorithms adopted to community detection. [ABSTRACT FROM AUTHOR]

Community structure is a common and important feature in many complex networks, including bipartite networks, which are used as a standard model for many empirical networks comprised of two types of nodes. In this paper, we propose a two-stage method for detecting community structure in bipartite networks. Firstly, we extend the widely-used Louvain algorithm to bipartite networks. The effectiveness and efficiency of the Louvain algorithm have been proved by many applications. However, there lacks a Louvain-like algorithm specially modified for bipartite networks. Based on bipartite modularity, a measure that extends unipartite modularity and that quantifies the strength of partitions in bipartite networks, we fill the gap by developing the Bi-Louvain algorithm that iteratively groups the nodes in each part by turns. This algorithm in bipartite networks often produces a balanced network structure with equal numbers of two types of nodes. Secondly, for the balanced network yielded by the first algorithm, we use an agglomerative clustering method to further cluster the network. We demonstrate that the calculation of the gain of modularity of each aggregation, and the operation of joining two communities can be compactly calculated by matrix operations for all pairs of communities simultaneously. At last, a complete hierarchical community structure is unfolded. We apply our method to two benchmark data sets and a large-scale data set from an e-commerce company, showing that it effectively identifies community structure in bipartite networks. [ABSTRACT FROM AUTHOR]

Community detection is of great importance to understand the structures and functions of networks. In this paper, a novel algorithm is proposed based on local similarity and degree clustering information. Local similarity is employed to measure the similarity between nodes and their neighbors in order to form communities within which nodes are closely connected. Degree clustering information, a hybrid criterion combining local neighborhood ratio with degree ratio, make a large number of nodes with low degree to embrace a small amount of nodes with high degree. Furthermore, each node in small scale communities has the duty to try to connect the nodes with high degree to expand communities, and finally the optimal community structure can be obtained. Simulation results on real and artificial networks show that the proposed algorithm has the excellent performance in terms of accuracy. [ABSTRACT FROM AUTHOR]

Community structure is one of the most important properties in networks, in which a node shares its most connections with the others in the same community. On the contrary, the anti-community structure means the nodes in the same group have few or no connections with each other. In Traditional Chinese Medicine (TCM), the incompatibility problem of herbs is a challenge to the clinical medication safety. In this paper, we propose a new anti-community detection algorithm, Random non-nEighboring nOde expansioN (REON), to find anti-communities in networks, in which a new evaluation criterion, anti-modularity, is designed to measure the quality of the obtained anti-community structure. In order to establish anti-communities in REON, we expand the node set by non-neighboring node expansion and regard the node set with the highest anti-modularity as an anti-community. Inspired by the phenomenon that the node with higher degree has greater contribution to the anti-modularity, an improved algorithm called REONI is developed by expanding node set by the non-neighboring node with the maximum degree, which greatly enhances the efficiency of REON. Experiments on synthetic and real-world networks demonstrate the superiority of the proposed algorithms over the existing methods. In addition, by applying REONI to the herb network, we find that it can discover incompatible herb combinations. [ABSTRACT FROM AUTHOR]

In this paper, based on growth and preferential attachment mechanism, we give a network generation model aiming at generating networks with community structure. There are three characteristics for the networks generated by the generation model. The first is that the community sizes can be nonuniform. The second is that there are bridge hubs in each community. The third is that the strength of community structure is adjustable. Next, we investigate rumor propagation behavior on the generated networks by performing Monte Carlo simulations to reveal the influence of bridge hubs, nonuniformity of community sizes and the strength of community structure on the dynamic behavior of the rumor propagation. We find that bridge hubs have outstanding performance in propagation speed and propagation size, and larger modularity can reduce rumor propagation. Furthermore, when the decay rate of rumor spreading β is large, the final density of the stiflers is larger if the rumor originates in larger community. Additionally, when on networks with different strengths of community structure, rumor propagation exhibits greater difference in the density of stiflers and in the peak prevalence if the decay rate β is larger. [ABSTRACT FROM AUTHOR]

Clustering algorithms for unsigned social networks which have only positive edges have been studied intensively. However, when a network has like/dislike, love/hate, respect/disrespect, or trust/distrust relationships, unsigned social networks with only positive edges are inadequate. Thus we model such kind of networks as signed networks which can have both negative and positive edges. Detecting the cluster structures of signed networks is much harder than for unsigned networks, because it not only requires that positive edges within clusters are as many as possible, but also requires that negative edges between clusters are as many as possible. Currently, we have few clustering algorithms for signed networks, and most of them requires the number of final clusters as an input while it is actually hard to predict beforehand. In this paper, we will propose a novel clustering algorithm called Eb & D for signed networks, where both the betweenness of edges and the density of subgraphs are used to detect cluster structures. A hierarchically nested system will be constructed to illustrate the inclusion relationships of clusters. To show the validity and efficiency of Eb & D, we test it on several classical social networks and also hundreds of synthetic data sets, and all obtain better results compared with other methods. The biggest advantage of Eb & D compared with other methods is that the number of clusters do not need to be known prior. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new algorithm to generate networks in which node degrees and community sizes can follow any arbitrary distribution. We compare the quality and efficiency of the proposed algorithm and the well-known algorithm by Lancichinetti et al. In contrast to the later one, the new algorithm, at the cost of accuracy, allows to generate two orders of magnitude larger networks in a reasonable time and it can be easily described analytically. [ABSTRACT FROM AUTHOR]

In recent years, the research of the community detection is not only on the structure that densely connected internally, but also on the structure of more patterns, such as heterogeneity, overlapping, core–periphery. In this paper, we build the network model based on the random graph models and propose an improved algorithm to infer the generalized community structures. We achieve it by introducing the generalized Bernstein polynomials and computing the latent parameters of vertices. The algorithm is tested both on the computer-generated benchmark networks and the real-world networks. Results show that the algorithm makes better performances on convergence speed and is able to discover the latent continuous structures in networks. [ABSTRACT FROM AUTHOR]

This paper takes central China power grid (CCPG) as an example, and analyzes the vulnerability of the power systems under terrorist attacks. To simulate the intelligence of terrorist attacks, a method of critical attack area identification according to community structures is introduced. Meanwhile, three types of vulnerability models and the corresponding vulnerability metrics are given for comparative analysis. On this basis, influence of terrorist attacks on different critical areas is studied. Identifying the vulnerability of different critical areas will be conducted. At the same time, vulnerabilities of critical areas under different tolerance parameters and different vulnerability models are acquired and compared. Results show that only a few number of vertex disruptions may cause some critical areas collapse completely, they can generate great performance losses the whole systems. Further more, the variation of vulnerability values under different scenarios is very large. Critical areas which can cause greater damage under terrorist attacks should be given priority of protection to reduce vulnerability. The proposed method can be applied to analyze the vulnerability of other infrastructure systems, they can help decision makers search mitigation action and optimum protection strategy. [ABSTRACT FROM AUTHOR]

Detecting hidden communities is important for the analysis of complex networks. However, many algorithms have been designed for single layer networks (SLNs) while just a few approaches have been designed for multiplex networks (MNs). In this paper, we propose an algorithm based on layer reduction for detecting communities on MNs, which is termed as LRCD-MNs. First, we improve a layer reduction algorithm termed as neighaggre to combine similar layers and keep others separated. Then, we use neighaggre to find the community structure hidden in MNs. Experiments on real-life networks show that neighaggre can obtain higher relative entropy than the other algorithm. Moreover, we apply LRCD-MNs on some real-life and synthetic multiplex networks and the results demonstrate that, although LRCD-MNs does not have the advantage in terms of modularity , it can obtain higher values of surprise , which is used to evaluate the quality of partitions of a network. [ABSTRACT FROM AUTHOR]

Since full coverage treatment is not feasible due to limited resources, we need to utilize an immunization strategy to effectively distribute the available vaccines. On the other hand, the structure of contact network among people has a significant impact on epidemics of infectious diseases (such as SARS and influenza) in a population. Therefore, network-based immunization strategies aim to reduce the spreading rate by removing the vaccinated nodes from contact network. Such strategies try to identify more important nodes in epidemics spreading over a network. In this paper, we address the effect of overlapping nodes among communities on epidemics spreading. The proposed strategy is an optimized random-walk based selection of these nodes. The whole process is local, i.e. it requires contact network information in the level of nodes. Thus, it is applicable to large-scale and unknown networks in which the global methods usually are unrealizable. Our simulation results on different synthetic and real networks show that the proposed method outperforms the existing local methods in most cases. In particular, for networks with strong community structures, high overlapping membership of nodes or small size communities, the proposed method shows better performance. [ABSTRACT FROM AUTHOR]

Social networks exhibit strong community structure. Many researches have been done to explore the impacts of community structure on information diffusion but few combined with human behaviors together. In this paper, we focus on how the individual interests’ changing behavior impacts the dynamics of information propagation. Firstly, we propose an information dissemination model considering both the community structure and individual interest shift where social reinforcement and time decaying are taken into account. The accuracy of the model is evaluated by comparing the simulation and theoretical results. Further, the numerical results illustrate that both the community structure and the interests changing behavior have effects on the outbreak size of the information dissemination. Specially, lower modularity and higher community connection density will accelerate the speed of information propagation especially when the information maximal lifetime is shorter. In addition, the changes of individual interests in the message have a great impact on the final density of the received through increasing or decreasing the number of satisfied individuals directly. What is more, our findings suggest that when the modularity of the network is higher and the community clustering coefficient is lower individual interest shift behavior will have a heavier effect on the spread scope. [ABSTRACT FROM AUTHOR]

Traditional community detection methods are often restricted in static network analysis. In fact, most of networks in real world obviously show dynamic characteristics with time passing. In this paper, we design a link community structure discovery algorithm in dynamic weighted networks, which can not only reveal the evolutionary link community structure, but also detect overlapping communities by mapping link communities to node communities. Meanwhile, our algorithm can also get the hierarchical structure of link communities by tuning a parameter. The proposed algorithm is based on weighted edge fitness and weighted partition density so as to determine whether to add a link to a community and whether to merge two communities to form a new link community. Experiments on both synthetic and real world networks demonstrate the proposed algorithm can detect evolutionary link community structure in dynamic weighted networks effectively. [ABSTRACT FROM AUTHOR]

Most complex networks contain community structures. Detecting these community structures is important for understanding and controlling the networks. Most community detection methods use network topology and edge density to identify optimal communities; however, these methods have a high computational complexity and are sensitive to network forms and types. To address these problems, in this paper, we propose an algorithm that uses an interaction optimization process to detect community structures in complex networks. This algorithm efficiently searches the candidates of optimal communities by optimizing the interactions of the members within each community based on the concept of greedy optimization. During this process, each candidate is evaluated using an interaction-based community model. This model quickly and accurately measures the difference between the quantity and quality of intra- and inter-community interactions. We test our algorithm on several benchmark networks with known community structures that include diverse communities detected by other methods. Additionally, after applying our algorithm to several real-world complex networks, we compare our algorithm with other methods. We find that the structure quality and coverage results achieved by our algorithm surpass those of the other methods. [ABSTRACT FROM AUTHOR]

Collective prediction algorithms have been used to improve performances when network structures are involved in prediction tasks. The training dataset of such tasks often contain information of content, links and labels, while the testing dataset have only content and link information. Conventional collective prediction algorithms conduct predictions based on the content of a node and the information of its direct neighbors with a base classifier. However, the information of some direct neighbor nodes may be not consistent with the target one. In addition, the information of indirect neighbors can be helpful when that of direct neighbors is scant. In this paper, instead of using information of direct neighbors, we propose to apply community structures in networks to prediction tasks. A community detection method is aggregated into the collective prediction process to improve prediction performance. Experimental results show that the proposed algorithm outperforms a number of standard prediction algorithms specially under conditions that labeled training dataset are limited. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new algorithm for community detection problems (CDPs) based on traveling salesman problems (TSPs), labeled as TSP-CDA. Since TSPs need to find a tour with minimum cost, cities close to each other are usually clustered in the tour. This inspired us to model CDPs as TSPs by taking each vertex as a city. Then, in the final tour, the vertices in the same community tend to cluster together, and the community structure can be obtained by cutting the tour into a couple of paths. There are two challenges. The first is to define a suitable distance between each pair of vertices which can reflect the probability that they belong to the same community. The second is to design a suitable strategy to cut the final tour into paths which can form communities. In TSP-CDA, we deal with these two challenges by defining a PageRank Distance and an automatic threshold-based cutting strategy. The PageRank Distance is designed with the intrinsic properties of CDPs in mind, and can be calculated efficiently. In the experiments, benchmark networks with 1000–10,000 nodes and varying structures are used to test the performance of TSP-CDA. A comparison is also made between TSP-CDA and two well-established community detection algorithms. The results show that TSP-CDA can find accurate community structure efficiently and outperforms the two existing algorithms. [ABSTRACT FROM AUTHOR]

In this paper, an evolving two-layer international economy network (IEN) consisting of international trade network (ITN) and international investment network (IIN) as layers, is constructed to investigate the world economy from 2001 to 2010. First, the structure analysis shows that the average partner numbers for both trade and investment are increasing year by year, and the average volume has a significant decrease in 2008 for investment and 2009 for trade. The IIN has longer average path length and dramatically lower edge density compared with the ITN, yet its clustering coefficient is larger in all years. Then, the regional relativity indicates that the longer the distance between two countries, the smaller trade and investment volumes they carry in are general, and the impact of the geographical distance gradually reduces as time goes on. Furthermore, the countries and regions are ranked by Pagerank in ITN, IIN and IEN to illustrate the roles they played. And finally, community structures are detected to visualize the global economic landscape, with countries and regions in the same community ranked according to the total volume of trade or investment. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm is proposed to detect one-mode community structures in bipartite networks, and to deduce which one-mode community structures are weighted. After analyzing the topological properties in bipartite networks, bipartite clustering triangular is introduced. First, bipartite networks are projected into two weighted one-mode networks by bipartite clustering triangular. Then all the maximal sub-graphs from two one-mode weighted networks are extracted and the maximal sub-graphs are merged together using a weighted clustering threshold. In addition, the proposed algorithm successfully finds overlapping vertices between one-mode communities. Experimental results using some real-world network data shows that the performance of the proposed algorithm is satisfactory. [ABSTRACT FROM AUTHOR]

Community detection gives us a simple way to understand complex networks’ structures. However, there is an imbalance problem in community detection. This paper first introduces the imbalance problem and then proposes a new measure to alleviate the imbalance problem. In addition, we study two variants of the measure and further analyze the resolution scale of community detection. Finally, we compare our approach with some state of the art methods on random networks as well as real-world networks for community detection. Both the theoretical analysis and the experimental results show that our approach achieves better performance for community detection. We also find that our approach tends to separate densely connected subgroups preferentially. [ABSTRACT FROM AUTHOR]

Community detection plays an important role in reflecting and understanding the topological structure of complex networks, and can be used to help mine the potential information in networks. This paper presents a Multiobjective Evolutionary Algorithm based on Affinity Propagation (APMOEA) which improves the accuracy of community detection. Firstly, APMOEA takes the method of affinity propagation (AP) to initially divide the network. To accelerate its convergence, the multiobjective evolutionary algorithm selects nondominated solutions from the preliminary partitioning results as its initial population. Secondly, the multiobjective evolutionary algorithm finds solutions approximating the true Pareto optimal front through constantly selecting nondominated solutions from the population after crossover and mutation in iterations, which overcomes the tendency of data clustering methods to fall into local optima. Finally, APMOEA uses an elitist strategy, called “external archive”, to prevent degeneration during the process of searching using the multiobjective evolutionary algorithm. According to this strategy, the preliminary partitioning results obtained by AP will be archived and participate in the final selection of Pareto-optimal solutions. Experiments on benchmark test data, including both computer-generated networks and eight real-world networks, show that the proposed algorithm achieves more accurate results and has faster convergence speed compared with seven other state-of-art algorithms. [ABSTRACT FROM AUTHOR]

Detection of community structures is beneficial to analyzing the structures and properties of networks. It is of theoretical interest and practical significance in modern science. So far, a large number of algorithms have been proposed to detect community structures in complex networks, but most of them are suitable for a specific network structure. In this paper, a novel method (called CDMIC) is proposed to detect the communities in un-weighted, weighted, un-directed, directed and signed networks by constructing a dissimilarity distance matrix of network and identifying community centers with maximizing modularity. For a given network, we first estimate the distance between all pairs of nodes for constructing the dissimilarity distance matrix of the network. Then, this distance matrix is input to the affinity propagation (AP) algorithm to extract a candidate center set of community. Thirdly, we rank these centers in descending order according to the sum of their availability and responsibility. Finally, we determine the community structure by selecting the center subset from the candidate center set in an incremental manner to make the modularity maximization. On three real-world networks and some synthetic networks, experimental results show that our CDMIC method has higher performance in terms of classification accuracy and normalized mutual information (NMI), and ability to tolerate the resolution limitation. [ABSTRACT FROM AUTHOR]

Community structures have important influence on the properties and dynamic characteristics of the complex networks. However, to the best of our knowledge, there is not much attention given to investigating the internal structure of communities in the literature. In this paper, we study community structures of more than twenty existing networks using ten commonly used community-detecting methods, and discovery that most communities have several leaders whose degrees are particularly large. We use statistical parameter, variance, to classify the communities as leader communities and self-organized communities. In a leader community, we defined the nodes with largest 10 % degree as its leaders. In our experiences, when removing the leaders, on average community’s internal edges are reduced by more than 40 % and inter-communities edges are reduced by more than 20 % . In addition, community’s average clustering coefficient decreases. These facts suggest that the leaders play an important role in keeping communities denser and more clustered, and it is the leaders that are more likely to link to other communities. Moreover, similar results for several random networks are obtained, and a theoretical lower bound of the lost internal edges is given. Our study shed the light on the further understanding and application of the internal community structure in complex networks. [ABSTRACT FROM AUTHOR]

Given a large network, dynamics of the network are determined by both nodes’ features and network connections. Some features could be extracted from node labels and other kinds of priori knowledge. But how to perform the feature classification without priori knowledge is a challenge. This paper addresses the key problem: how do we conduct role extraction in networks with only edge connections known? On the basis of behavior differences in dynamics, nodes are classified into three role groups: Leaders(L), Communicators(C) and Members(M). Unlike traditional community detections, we detect overlapping communities by link clustering first and then classify nodes according to the community entropy, which describes the disorder of how many different communities a node connects to. We propose a time saving and unsupervised learning approach for automatically discovering nodes’ roles based solely on network topology. The effectiveness of this method is demonstrated on six real-world networks through pinning control. By controlling communicator nodes, the controllability is enhanced and the cost for control is reduced obviously in networks with strong community structure. [ABSTRACT FROM AUTHOR]

In this paper, we propose two novel models of epidemic spreading by considering the activity-driven and the network modular. Firstly, we consider the susceptible–infected–susceptible ( S I S ) contagion model and derive analytically the epidemic threshold. The results indicate that the epidemic threshold only involves with the value of the spread rate and the recovery rate. In addition, the asymptotic refractory density of infected nodes in the different communities exhibits different trends with the change of the modularity-factor. Then, the infected-driven vaccination model is presented. Simulation results illustrate that the final density of vaccination will increase with the increase of the response strength of vaccination. Moreover, the final infected density in the original-infected-community shows different trends with the change of the response strength of vaccination and the spreading rate. The infected-driven vaccination is a good way to control the epidemic spreading. [ABSTRACT FROM AUTHOR]

Any network studied in the literature is inevitably just a sampled representative of its real-world analogue. Additionally, network sampling is lately often applied to large networks to allow for their faster and more efficient analysis. Nevertheless, the changes in network structure introduced by sampling are still far from understood. In this paper, we study the presence of characteristic groups of nodes in sampled social and information networks. We consider different network sampling techniques including random node and link selection, network exploration and expansion. We first observe that the structure of social networks reveals densely linked groups like communities, while the structure of information networks is better described by modules of structurally equivalent nodes. However, despite these notable differences, the structure of sampled networks exhibits stronger characterization by community-like groups than the original networks, irrespective of their type and consistently across various sampling techniques. Hence, rich community structure commonly observed in social and information networks is to some extent merely an artifact of sampling. [ABSTRACT FROM AUTHOR]

Identifying highly susceptible individuals in spreading processes is of great significance in controlling outbreaks. In this paper, we explore the susceptibility of people in susceptible-infectious-recovered (SIR) and rumor spreading dynamics. We first study the impact of community structure on people’s susceptibility. Although the community structure can reduce the number of infected people for same infection rate, it will not significantly affect nodes’ susceptibility. We find the susceptibility of individuals is sensitive to the choice of spreading dynamics. For SIR spreading, since the susceptibility is highly correlated to nodes’ influence, the topological indicator k -shell can better identify highly susceptible individuals, outperforming degree, betweenness centrality and PageRank. In contrast, in rumor spreading model, where nodes’ susceptibility and influence have no clear correlation, degree performs the best among considered topological measures. Our finding highlights the significance of both topological features and spreading mechanisms in identifying highly susceptible population. [ABSTRACT FROM AUTHOR]

Community detection plays an important role in research on network characteristics and in the mining of network information. A variety of algorithms have previously been proposed, but with the continuous growth of network scale, few of them can detect community structure efficiently. Additionally, most of these algorithms only consider non-overlapping community structures in networks. This paper addresses these problems by proposing a new algorithm, based on node membership grade and sub-communities integration, to detect community structure in large-scale networks. The proposed algorithm firstly introduces two functions based on the local information of each node in networks, namely neighboring inter-nodes membership function f MS − NN and node-to-community membership function f MS − NC . Firstly, local potential’s complete sub-graphs are efficiently mined using the function f MS − NN , and then these small graphs are merged into larger ones in light of local modularity. Secondly, incorrectly divided nodes are modified according to function f MS − NN . Additionally, by adjusting the parameters in f MS − NC , we can accurately obtain both non-overlapping communities and overlapping communities. Furthermore, the proposed algorithm employs a framework resembling label propagation, which has low time complexity and is suitable for detecting communities in large-scale networks. Experimental results on both artificial networks and real networks indicate the accuracy and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, the transition of synchronizing path of delay-coupled chaotic oscillators in a scale-free network is highlighted. Mainly, through the critical transmission delay makes chaotic oscillators be coupled on the edge of stability, we find that the transition of synchronizing path is abnormal , which is characterized by the following evidences: (a) synchronization process starts with low-degree rather than high-degree ones; (b) the high-degree nodes do not undertake the role of hub; (c) the synchronized subnetworks show a poor small-world property as a result of hubs’ absence; (d) the clustering synchronization behavior emerges even community structure is absent in the scale-free network. This abnormal synchronizing path suggests that the diverse synchronization behaviors occur in the same topology, which implies that the relationship between dynamics and structure of network is much more complicated than the common sense that the structure is the foundation of dynamics. Moreover, it also reveals the potential connection from the transition of synchronization behavior to disorder in real complex networks, e.g. Alzheimer disease. [ABSTRACT FROM AUTHOR]

The participation of a node in more than one community is a common phenomenon in complex networks. However most existing methods, fail to identify nodes with multiple community affiliation, correctly. In this paper, a unique method to define overlapping community in complex networks is proposed, using the overlapping neighborhood ratio to represent relations between nodes. Matrix factorization is then utilized to assign nodes into their corresponding community structures. Moreover, the proposed method demonstrates the use of Perron clusters to estimate the number of overlapping communities in a network. Experimental results in real and artificial networks show, with great accuracy, that the proposed method succeeds to recover most of the overlapping communities existing in the network. [ABSTRACT FROM AUTHOR]

Immunizing important nodes has been shown to be an effective solution to suppress the epidemic spreading. Most studies focus on the globally important nodes in a network, but neglect the locally important nodes in different communities. We claim that given the temporal community feature of opportunistic social networks (OSN), this strategy has a biased understanding of the epidemic dynamics, leading us to conjecture that it is not “the more central, the better” for the implementation of control strategy. In this paper, we track the evolution of community structure and study the effect of community-based immunization strategy on epidemic spreading. We first break the OSN traces down into different communities, and find that the community structure helps to delay the outbreak of epidemic. We then evaluate the local importance of nodes in communities, and show that immunizing nodes with high local importance can remarkably suppress the epidemic. More interestingly, we find that high local importance but non-central nodes play a big role in epidemic spreading process, removing them improves the immunization efficiency by 25% to 150% at different scenarios. [ABSTRACT FROM AUTHOR]

Community structure is a common phenomenon in complex networks, and it has been shown that some communities in complex networks often overlap each other. So in this paper we propose a new algorithm to detect overlapping community structure in complex networks. To identify the overlapping community structure, our algorithm firstly extracts fully connected sub-graphs which are maximal sub-graphs from original networks. Then two maximal sub-graphs having the key pair-vertices can be merged into a new larger sub-graph using some belonging degree functions. Furthermore we extend the modularity function to evaluate the proposed algorithm. In addition, overlapping nodes between communities are founded successfully. Finally we report the comparison between the modularity and the computational complexity of the proposed algorithm with some other existing algorithms. The experimental results show that the proposed algorithm gives satisfactory results. [ABSTRACT FROM AUTHOR]

Detecting evolutionary community structure in dynamic weighted networks is important for understanding the structure and functions of networks. In this paper, an algorithm which considers the historic community structure of networks is developed to detect evolutionary community structure in dynamic weighted networks. In the proposed algorithm, two measures are proposed to determine whether to add a node to a community and whether to merge two communities to form a new community. The proposed algorithm can automatically discover evolutionary community structure in weighted networks whose number of nodes and communities is changing over time and does not need to determine the number of communities in advance. The algorithm is tested using a synthetic network and two real-word complex networks. Experimental results demonstrate that the proposed algorithm can discover evolutionary community structure in dynamic weighted networks effectively. [ABSTRACT FROM AUTHOR]

Abstract: Community detection is one of the most important problems in complex networks. Many algorithms have been proposed in the last decade, and most of them focus on the non-overlapping community structures in the early days. Overlapping and hierarchical structures are another two important properties in complex networks, which have attracted researchers’ extensive concern in recent years. In this paper, we proposed a two-stage method which can detect the hierarchical, non-overlapping and overlapping community structures in complex networks. In this method, the CNM algorithm, a fast hierarchical agglomerative algorithm proposed by Clauset, Newman and Moore, is used in the first stage. In the second stage, a new evaluation function named as influence coefficient based on the local community structure is proposed, which can get the overlapping community structures at different overlapping levels by adjusting a tunable parameter. Besides, the proposed evaluation function can detect the wrongly classified nodes in the partition of the first stage and correct them. Finally, the computational complexity of the algorithm is low. The experimental results on both synthetic and real-world network datasets show the efficiency of our method. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a novel measure that integrates both the concept of closed walks and clustering coefficients to replace the edge betweenness in the well-known divisive hierarchical clustering algorithm, the Girvan and Newman method (GN). The edges with the lowest value are removed iteratively until the network is degenerated into isolated nodes. The experimental results on computer generated networks and real-world networks showed that our method makes a better tradeoff of accuracy and runtime. Based on the analysis of the results, we observe that the nontrivial closed walks of order three and four can be considered as the basic elements in constructing community structures. Meanwhile, we discover that those nontrivial closed walks outperform trivial closed walks in the task of analyzing the structure of networks. The double peak structure problem is mentioned in the last part of the article. We find that our proposed method is a novel way to solve the double peak structure problem. Our work can provide us with a new perspective for understanding community structure in complex networks. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a weighted modularity based on the similarity of weights on edges and a threshold coefficient 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 , we observe that optimization on the 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. [Copyright &y& Elsevier]

Abstract: Communities are groups of nodes forming tightly connected units in networks. Some nodes can be shared between different communities of a network. The presence of overlapping nodes and their associated membership diversity is a common characteristic of social networks. Analyzing these overlapping structures can reveal valuable information about the intrinsic features of realistic complex networks, especially social networks. In this paper, we propose a novel algorithm that is able to detect overlapping and non-overlapping community structures in complex networks. This algorithm uses a number of agents for investigation of the input network. These agents consider different nodes’ closeness in their investigations. Various experiments are carried out on both synthetic and real-world networks that prove that the proposed algorithm outperforms most state-of-the-art algorithms of this field both in terms of the accuracy and execution time. [Copyright &y& Elsevier]

Abstract: Community detection has become an important methodology to understand the organization and function of various real-world networks. The label propagation algorithm (LPA) is an almost linear time algorithm proved to be effective in finding a good community structure. However, LPA has a limitation caused by its one-hop horizon. Specifically, each node in LPA adopts the label shared by most of its one-hop neighbors; much network topology information is lost in this process, which we believe is one of the main reasons for its instability and poor performance. Therefore in this paper we introduce a measure named weighted coherent neighborhood propinquity (weighted-CNP) to represent the probability that a pair of vertices are involved in the same community. In label update, a node adopts the label that has the maximum weighted-CNP instead of the one that is shared by most of its neighbors. We propose a dynamic and adaptive weighted-CNP called entropic-CNP by using the principal of entropy to modulate the weights. Furthermore, we propose a framework to integrate the weighted-CNP in other algorithms in detecting community structure. We test our algorithm on both computer-generated networks and real-world networks. The experimental results show that our algorithm is more robust and effective than LPA in large-scale networks. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new approach to extract communities in the complex networks with considerable accuracy. We introduce the core-vertex and the intimate degree between the community and its neighboring vertices. First, we find the core-vertices as the initial community. These core-vertices are then expanded using intimate degree function during extracting community structure from the given network. In addition, our algorithm successfully finds common nodes between communities. Experimental results using some real-world networks data shows that the performance of our algorithm is satisfactory. [Copyright &y& Elsevier]