New method for counting the number of spanning trees in a two-tree network

The number of spanning trees is an important quantity characterizing the reliability of a network. Generally, the number of spanning trees in a network can be obtained by directly calculating a related determinant corresponding to the network. However, for a large network, evaluating the relevant determinant is intractable. In this paper, we investigate the number of spanning trees in two-tree networks. We first give a new algorithm which avoids the laborious computation of the determinant for counting the number of spanning trees. Using the algorithm, we can obtain the number of spanning trees of any two-tree network in linear time. The result shows that the computation complexity is O(n)$O\left(n\right)$, which is better than that of the matrix tree theorem with O(n²)$O\left(n^2\right)$, where n$n$ is the number of steps. We then characterize two-tree networks with the maximum and minimum numbers of spanning trees. Denote by P(t)$P\left(t\right)$ and K(t)$K\left(t\right)$, respectively, the two-tree networks of t+2$t+2$ vertices with the maximum and minimum numbers of spanning trees. Denote by PA$PA$ and EN$EN$, respectively, the two-tree network of t+2$t+2$ vertices generated by preferential attachment and by equiprobability attachment. By algorithmic analysis and through simulations, we conjecture that _NST(K(t))≤_NST(PA)≤_NST(EN)≤_NST(P(t))$N_{ST}\left(K\left(t\right)\right)\le N_{ST}\left(PA\right)\le N_{ST}\left(EN\right)\le N_{ST}\left(P\left(t\right)\right)$ as t$t$ tends to infinity, where _NST(G)$N_{ST}\left(G\right)$ is the number of spanning trees of G$G$. As an application of the algorithm, we give the formula of the number of spanning trees of a particular small-world network.     

Semi-supervised clustering algorithm for community structure detection in complex networks

Discovering a community structure is fundamental for uncovering the links between structure and function in complex networks. In this paper, we discuss an equivalence of the objective functions of the symmetric nonnegative matrix factorization (SNMF) and the maximum optimization of modularity density. Based on this equivalence, we develop a new algorithm, named the so-called SNMF-SS, by combining SNMF and a semi-supervised clustering approach. Previous NMF-based algorithms often suffer from the restriction of measuring network topology from only one perspective, but our algorithm uses a semi-supervised mechanism to get rid of the restriction. The algorithm is illustrated and compared with spectral clustering and NMF by using artificial examples and other classic real world networks. Experimental results show the significance of the proposed approach, particularly, in the cases when community structure is obscure.     

Phase transition model for community detection

Motivated by social and biological interactions, a novel type of phase transition model is provided in order to investigate the emergence of the clustering phenomenon in networks. The model has two types of interactions: one is attractive and the other is repulsive. In each iteration, the phase of a node (or an agent) moves toward the average phase of its neighbors and moves away from the average phase of its non-neighbors. The velocities of the two types of phase transition are controlled by two parameters, respectively. It is found that the phase transition phenomenon is closely related to the topological structure of the underlying network, and thus can be applied to identify its communities and overlapping groups. By giving each node of the network a randomly generated initial phase and updating these phases by the phase transition model until they reach stability, one or two communities will be detected according to the nodes’ stable phases, confusable nodes are moved into a set named _Of$O_f$. By removing the detected communities and the nodes in _Of$O_f$, another one or two communities will be detected by an iteration of the algorithm, …. In this way, all communities and the overlapping nodes are detected. Simulations on both real-world networks and the LFR benchmark graphs have verified the efficiency of the proposed scheme.     

Currency crises and the evolution of foreign exchange market: Evidence from minimum spanning tree

We examined the time series properties of the foreign exchange market for 1990-2008 in relation to the history of the currency crises using the minimum spanning tree (MST) approach and made several meaningful observations about the MST of currencies. First, around currency crises, the mean correlation coefficient between currencies decreased whereas the normalized tree length increased. The mean correlation coefficient dropped dramatically passing through the Asian crisis and remained at the lowered level after that. Second, the Euro and the US dollar showed a strong negative correlation after 1997, implying that the prices of the two currencies moved in opposite directions. Third, we observed that Asian countries and Latin American countries moved away from the cluster center (USA) passing through the Asian crisis and Argentine crisis, respectively.     

Growth curve based label propagation algorithm for community detection

How to better and faster identify the community structure is a hot issue in complex networks. During the past decades, various attempts have been made to solve this issue. Amongst them, without doubt, label propagation algorithm (LPA) is one of the most satisfying answers, especially for large-scale networks. However, it has one major flaw that when the community structure is not clear enough, a monster community tends to form. To address this issue, we set a growth curve for communities, gradually increasing from a low capacity to a higher capacity over time. Further, we improve the mechanism of label choosing for small communities to escape from local maximum. The experimental results on both synthetic and real networks demonstrate that our algorithm not only enhances the detection ability of the traditional label propagation algorithm, but also improves the quality of the identified communities.     

Sovereign debt crisis in the European Union: A minimum spanning tree approach

In the wake of the financial crisis, sovereign debt crisis has emerged and is severely affecting some countries in the European Union, threatening the viability of the euro and even the EU itself. This paper applies recent developments in econophysics, in particular the minimum spanning tree approach and the associate hierarchical tree, to analyze the asynchronization between the four most affected countries and other resilient countries in the euro area. For this purpose, daily government bond yield rates are used, covering the period from April 2007 to October 2010, thus including yield rates before, during and after the financial crises. The results show an increasing separation of the two groups of euro countries with the deepening of the government bond crisis.     

Fuzzy analysis of community detection in complex networks

A snowball algorithm is proposed to find community structures in complex networks by introducing the definition of community core and some quantitative conditions. A community core is first constructed, and then its neighbors, satisfying the quantitative conditions, will be tied to this core until no node can be added. Subsequently, one by one, all communities in the network are obtained by repeating this process. The use of the local information in the proposed algorithm directly leads to the reduction of complexity. The algorithm runs in O(n+m) time for a general network and O(n) for a sparse network, where n is the number of vertices and m is the number of edges in a network. The algorithm fast produces the desired results when applied to search for communities in a benchmark and five classical real-world networks, which are widely used to test algorithms of community detection in the complex network. Furthermore, unlike existing methods, neither global modularity nor local modularity is utilized in the proposal. By converting the considered problem into a graph, the proposed algorithm can also be applied to solve other cluster problems in data mining.     

Counting spanning trees in a small-world Farey graph

The problem of spanning trees is closely related to various interesting problems in the area of statistical physics, but determining the number of spanning trees in general networks is computationally intractable. In this paper, we perform a study on the enumeration of spanning trees in a specific small-world network with an exponential distribution of vertex degrees, which is called a Farey graph since it is associated with the famous Farey sequence. According to the particular network structure, we provide some recursive relations governing the Laplacian characteristic polynomials of a Farey graph and its subgraphs. Then, making use of these relations obtained here, we derive the exact number of spanning trees in the Farey graph, as well as an approximate numerical solution for the asymptotic growth constant characterizing the network. Finally, we compare our results with those of different types of networks previously investigated.     

Ant colony clustering with fitness perception and pheromone diffusion for community detection in complex networks

Community structure detection in complex networks has been intensively investigated in recent years. In this paper, we propose an adaptive approach based on ant colony clustering to discover communities in a complex network. The focus of the method is the clustering process of an ant colony in a virtual grid, where each ant represents a node in the complex network. During the ant colony search, the method uses a new fitness function to percept local environment and employs a pheromone diffusion model as a global information feedback mechanism to realize information exchange among ants. A significant advantage of our method is that the locations in the grid environment and the connections of the complex network structure are simultaneously taken into account in ants moving. Experimental results on computer-generated and real-world networks show the capability of our method to successfully detect community structures.     

Quantum inspired evolutionary algorithm for community detection in complex networks

Community structure is indispensable to discover the potential property of complex network systems. In this paper we propose two algorithms (QIEA-net and iQIEA-net) to discover communities in social networks by optimizing modularity. Unlike many existing methods, the proposed algorithms adopt quantum inspired evolutionary algorithm (QIEA) to optimize a population of solutions and do not need to give the number of community beforehand, which is determined by optimizing the value of modularity function and needs no human intervention. In order to accelerate the convergence speed, in iQIEA-net, we apply the result of classical partitioning algorithm as a guiding quantum individual, which can instruct other quantum individuals' evolution. We demonstrate the potential of two algorithms on five real social networks. The results of comparison with other community detection algorithms prove our approaches have very competitive performance.     

Modelling of weighted evolving networks with community structures

Many social and biological networks consist of communities–groups of nodes within which links are dense but among which links are sparse. It turns out that most of these networks are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the link weights among their nodes. Recently, there are considerable interests in the study of properties as well as modelling of such networks with community structures. To our knowledge, however, no study of any weighted network model with such a community structure has been presented in the literature to date. In this paper, we propose a weighted evolving network model with a community structure. The new network model is based on the inner-community and inter-community preferential attachments and preferential strengthening mechanism. Simulation results indicate that this network model indeed reflect the intrinsic community structure, with various power-law distributions of the node degrees, link weights, and node strengths.     

Comovements in government bond markets: A minimum spanning tree analysis

The concept of a minimum spanning tree (MST) is used to study patterns of comovements for a set of twenty government bond market indices for developed North American, European, and Asian countries. We show how the MST and its related hierarchical tree evolve over time and describe the dynamic development of market linkages. Over the sample period, 1993-2008, linkages between markets have decreased somewhat. However, a subset of European Union (EU) bond markets does show increasing levels of comovements. The evolution of distinct groups within the Eurozone is also examined. The implications of our findings for portfolio diversification benefits are outlined.     

Detecting the community structure in complex networks based on quantum mechanics

In this paper, we develop a novel method to detect the community structure in complex networks. This approach is based on the combination of kernel-based clustering using quantum mechanics, the spectral clustering technique and the concept of the Bayesian information criterion. We test the proposed algorithm on Zachary’s karate club network and the world of American college football. Experimental results indicate that our algorithm is efficient and effective at finding both the optimal number of clusters, and the best clustering of community structures.     

Traffic dynamics in scale-free networks with tunable strength of community structure

In this paper we systematically investigate the impact of community structure on traffic dynamics in scale-free networks based on local routing strategy. A growth model is introduced to construct scale-free networks with tunable strength of community structure, and a packet routing strategy with a parameter α is used to deal with the navigation and transportation of packets simultaneously. Simulations show that the maximal network capacity stands at α=−1 in the case of identical vertex capacity and monotonously decreases with the strength of community structure which suggests that the networks with fuzzy community structure (i.e., community strength is weak) are more efficient in delivering packets than those with pronounced community structure. To explain these results, the distribution of packets of each vertex is carefully studied. Our results indicate that the moderate strength of community structure is more convenient for the information transfer of real complex systems.     

Limitation of multi-resolution methods in community detection

Community detection is of considerable interest for analyzing the structure and function of complex networks. Recently, a type of multi-resolution methods in community detection was introduced, which can adjust the resolution of modularity by modifying the modularity function with tunable resolution parameters, such as those proposed by Arenas, Fernández and Gómez and by Reichardt and Bornholdt. In this paper, we show that these methods still have the intrinsic limitation–large communities may have been split before small communities become visible–because it is at the cost of the community stability that the enhancement of the modularity resolution is obtained. The theoretical results indicated that the limitation depends on the degree of interconnectedness of small communities and the difference between the sizes of small communities and of large communities, while independent of the size of the whole network. These findings have been confirmed in several example networks, where communities even are full-completed sub-graphs.     

Recursive filtration method for detecting community structure in networks

Community detection is a topic of considerable recent interest within complex networks, but most methods proposed so far are divisive and agglomerative methods which delete only one edge each time to split the network, or agglomerating only one node each time until no individual node remains. Unlike those, we propose a method to split networks in parallel by deleting many edges in each filtration operation, and propose a community recursive coefficient (CRC) denoted by M instead of Q (modularity) to quantify the effect of the splitting results in this paper. We proved that recursive optimizing of the local M is equivalent to acquiring the maximal global Q value corresponding to good divisions. For a network with m edges, c communities and arbitrary topology, the method split the network at most c+1 times and detected the community structure in time O(m²+(c+1)m). We give several example applications, and show that the method can detect local communities according to the densities of external links to them in increasing order especially in large networks.     

Detecting community structure in complex networks based on a measure of information discrepancy

Properties of complex networks, such as small-world property, power-law degree distribution, network transitivity, and network- community structure which seem to be common to many real-world networks have attracted great interest among researchers. In this study, global information of the networks is considered by defining the profile of any node based on the shortest paths between it and all the other nodes in the network; then a useful iterative procedure for community detection based on a measure of information discrepancy and the popular modular function Q is presented. The new iterative method does not need any prior knowledge about the community structure and can detect an appropriate number of communities, which can be hub communities or non-hub communities. The computational results of the method on real networks confirm its capability.     

Detecting community structure in complex networks via node similarity

The detection of the community structure in networks is beneficial to understand the network structure and to analyze the network properties. Based on node similarity, a fast and efficient method for detecting community structure is proposed, which discovers the community structure by iteratively incorporating the community containing a node with the communities that contain the nodes with maximum similarity to this node to form a new community. The presented method has low computational complexity because of requiring only the local information of the network, and it does not need any prior knowledge about the communities and its detection results are robust on the selection of the initial node. Some real-world and computer-generated networks are used to evaluate the performance of the presented method. The simulation results demonstrate that this method is efficient to detect community structure in complex networks, and the ZLZ metrics used in the proposed method is the most suitable one among local indices in community detection.     

Response of scale-free networks with community structure to external stimuli

The response of scale-free networks with community structure to external stimuli is studied. By disturbing some nodes with different strategies, it is shown that the robustness of this kind of network can be enhanced due to the existence of communities in the networks. Some of the response patterns are found to coincide with topological communities. We show that such phenomena also occur in the cat brain network which is an example of a scale-free like network with community structure. Our results provide insights into the relationship between network topology and the functional organization in complex networks from another viewpoint.     

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K-L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.