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.     

A validity index approach for network partitions

The validity index has been used to evaluate the fitness of partitions produced by clustering algorithms for points in Euclidean space. In this paper, we propose a new validity index for network partitions, which can provide a measure of goodness for the community structure of networks. It is defined as a product of two factors, and involves the compactness and separation for each partition. The simulated annealing strategy is used to minimize such a validity index function in coordination with our previous k-means algorithm based on the optimal reduction of a random walker Markovian dynamics on the network. It is demonstrated that the algorithm can efficiently find the community structure during the cooling process. The number of communities can be automatically determined without any prior knowledge of the community structure. Moreover, the algorithm is successfully applied to three real-world networks.     

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 communities in clustered networks based on group action on set

In this paper, we propose a well targeted algorithm (GAS algorithm) for detecting communities in high clustered networks by presenting group action technology on community division. During the processing of this algorithm, the underlying community structure of a clustered network emerges simultaneously as the corresponding partition of orbits by the permutation groups acting on the node set are achieved. As the derivation of the orbit partition, an algebraic structure r-cycle can be considered as the origin of the community. To be a priori estimation for the community structure of the algorithm, the community separability is introduced to indicate whether a network has distinct community structure. By executing the algorithm on several typical networks and the LFR benchmark, it shows that this GAS algorithm can detect communities accurately and effectively in high clustered networks. Furthermore, we compare the GAS algorithm and the clique percolation algorithm on the LFR benchmark. It is shown that the GAS algorithm is more accurate at detecting non-overlapping communities in clustered networks. It is suggested that algebraic techniques can uncover fresh light on detecting communities in complex networks.     

The effect of weight on community structure of networks

The effect of weight on community structures is investigated in this paper. We use weighted modularity Q^w$Q^w$ to evaluate the partitions and weighted extremal optimization algorithm to detect communities. Starting from empirical and idealized weighted networks, the matching between weights and edges are disturbed. Then using similarity function S to measure the difference between community structures, it is found that the redistribution of weights does strongly affect the community structure especially in dense networks. This indicates that the community structure in networks is a suitable property to reflect the role of weight.     

加权网络权重自相似评判函数及其社团结构检测

提出了权重自相似性加权网络社团结构评判函数,并基于该函数提出一种谱分析算法检测社团结构,结果表明算法能将加权网络划分为同一社团内边权值分布均匀,而社团间边权值分布随机的社团结构.通过建立具有社团结构的加权随机网络分析了该算法的准确性,与WEO和WGN算法相比,在评判权重自相似的阈值系数取较小时,该算法具有较高的准确性.对于一个具有n个节点和c个社团的加权网络,社团结构检测的复杂度为O(cn2/2).通过设置评判权重自相似的阈值系数,可检测出能反映节点联系稳定性的层化性社团结构.这与传统意义上只将加权网络划分为社团中边权值较大而社团间边权值较小的标准不同,从另一个角度更好地提取了加权网络的结构信息.     

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 from coherent oscillation of excitable systems

Many networks are proved to have community structures. On the basis of the fact that the dynamics on networks are intensively affected by the related topology, in this paper the dynamics of excitable systems on networks and a corresponding approach for detecting communities are discussed. Dynamical networks are formed by interacting neurons; each neuron is described using the FHN model. For noisy disturbance and appropriate coupling strength, neurons may oscillate coherently and their behavior is tightly related to the community structure. Synchronization between nodes is measured in terms of a correlation coefficient based on long time series. The correlation coefficient matrix can be used to project network topology onto a vector space. Then by the K-means cluster method, the communities can be detected. Experiments demonstrate that our algorithm is effective at discovering community structure in artificial networks and real networks, especially for directed networks. The results also provide us with a deep understanding of the relationship of function and structure for dynamical networks.     

Fuzzy overlapping community detection based on local random walk and multidimensional scaling

A fuzzy overlapping community is an important kind of overlapping community in which each node belongs to each community to different extents. It exists in many real networks but how to identify a fuzzy overlapping community is still a challenging task. In this work, the concept of local random walk and a new distance metric are introduced. Based on the new distance measurement, the dissimilarity index between each node of a network is calculated firstly. Then in order to keep the original node distance as much as possible, the network structure is mapped into low-dimensional space by the multidimensional scaling (MDS). Finally, the fuzzy c$c$-means clustering is employed to find fuzzy communities in a network. The experimental results show that the proposed algorithm is effective and efficient to identify the fuzzy overlapping communities in both artificial networks and real-world networks.     

Assortativity of complementary graphs

Newman's measure for (dis)assortativity, the linear degree correlationρ _D , is widely studied although analytic insight into the assortativity of an arbitrary network remains far from well understood. In this paper, we derive the general relation (2), (3) and Theorem 1 between the assortativity ρ _D (G) of a graph G and the assortativityρ _D (G ^c) of its complement G ^c. Both ρ _D (G) and ρ _D (G ^c) are linearly related by the degree distribution in G. When the graph G(N,p) possesses a binomial degree distribution as in the Erd?s-Rényi random graphs G _p (N), its complementary graph G _p ^c (N) = G _{1- p} (N) follows a binomial degree distribution as in the Erd?s-Rényi random graphs G _{1- p} (N). We prove that the maximum and minimum assortativity of a class of graphs with a binomial distribution are asymptotically antisymmetric: ρ _max(N,p) = -ρ _min(N,p) for N → ∞. The general relation (3) nicely leads to (a) the relation (10) and (16) between the assortativity range ρ _max(G)–ρ _min(G) of a graph with a given degree distribution and the range ρ _max(G ^c)–ρ _min(G ^c) of its complementary graph and (b) new bounds (6) and (15) of the assortativity. These results together with our numerical experiments in over 30 real-world complex networks illustrate that the assortativity range ρ _max–ρ _min is generally large in sparse networks, which underlines the importance of assortativity as a network characterizer.     

Crossover scaling,correlation function and connectivity in dilute low temperature ferromagnets

For quenched dilute ferromagnets with a fractionp of spins (nearest neighbor exchange energyJ) and a fraction 1 —p of randomly distributed nonmagnetic atoms, a crossover assumption similar to tricritical scaling theory relates the critical exponents of zero temperature percolation theory to the low temperature critical amplitudes and exponents near the critical lineT _c (p)>0. For example, the specific heat amplitude nearT _c (p) is found to vanish, the susceptibility amplitude is found to diverge forT _c (p →p _c ) → 0. (Typically,p _c =20%.) AtT=0 the spin-spin correlation function is argued from a droplet picture to obey scaling homogeneity but (at fixed distance) not to vary like the energy; instead it varies as const + (p _c —p)^2β +? for fixed small distances. A generalization of the correlation function to finite temperatures nearT _c (p) allows to estimate the number of effective percolation channels connecting two sites in the infinite (percolating) network forp>p _c ; this in turn gives, via a dynamical scaling argument, a good approximation for theT=0 percolation exponent 1.6 in the conductivity of random three-dimensional resistor networks. This channel approximation also givesΦ=2 for the crossover exponent; i.e. exp(?2J/kT _c (p)) is an analytic function ofp nearp=p _c . An appendix shows that cluster-cluster correlations atT=0 (excluded volume effects) are responsible for the difference between percolation exponents and the (pure) Ising exponents atT _c (p=1).     

Detecting overlapping communities of weighted networks via a local algorithm

Identification of communities is significant in understanding the structures and functions of networks. Since some nodes naturally belong to several communities, the study of overlapping communities has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. In this paper, an overlapping communities detecting algorithm is proposed whose main strategies are finding an initial partial community from a node with maximal node strength and adding tight nodes to expand the partial community. Seven real-world complex networks and one synthetic network are used to evaluate the algorithm. Experimental results demonstrate that the algorithm proposed is efficient for detecting overlapping communities in weighted networks.     

Thermal expansion of dysprosium tetraboride

The temperature variations of the interplanar spacings a(T) and c(T) in the crystal lattice of dysprosium tetraboride have been studied using X-ray diffraction in the temperature range 5?C300 K. Anomalous variations of a(T) and c(T) in the temperature range of magnetic transformations, anisotropy of the thermal expansion of DyB₄, and the monoclinic distortion of the crystal structure at low temperatures have been revealed. The magnitudes of the spontaneous magnetostriction, the thermal expansion coefficients ??a and ??c, and the exchange integrals Y _a and Y _c have been determined.     

Ubiquitousness of link-density and link-pattern communities in real-world networks

Many networks are characterized by the presence of communities, densely intra-connected groups with sparser inter-connections between groups. We propose a community overlay network representation to capture large-scale properties of communities. A community overlay G _o can be constructed upon a network G, called the underlying network, by (a) aggregating each community in G as a node in the overlay G _o ; (b) connecting two nodes in the overlay if the corresponding two communities in the underlying network have a number of direct links in between, (c) assigning to each node/link in the overlay a node/link weight, which represents e.g. the percentage of links in/between the corresponding underlying communities. The community overlays have been constructed upon a large number of real-world networks based on communities detected via five algorithms. Surprisingly, we find the following seemingly universal properties: (i) an overlay has a smaller degree-degree correlation than its underlying network ρ _o (D _l+, D _l−) < ρ(D _l+, D _l−) and is mostly disassortative ρ _o (D _l+, D _l−) < 0; (ii) a community containing a large number W _i of nodes tends to connect to many other communities ρ _o (W _i , D _i ) > 0. We explain the generic observation (i) by two facts: (1) degree-degree correlation or assortativity tends to be positively correlated with modularity; (2) by aggregating each community as a node, the modularity in the overlay is reduced and so is the assortativity. The observation (i) implies that the assortativity of a network depends on the aggregation level of the network representation, which is illustrated by the Internet topology at router and AS level.     

Observation of a transition from BCS to HTSC-like superconductivity in Ba1 − x KxBiO3 single crystals

The temperature dependences of the upper critical field B _c2(T) and surface impedance Z(T) = R(T) + iX(T) have been measured in Ba_{1 ? x} K_xBiO₃ single crystals with transition temperatures 6 ≤ T _c ≤ 32 K (0.6 > x > 0.4). A transition from the BCS to an unusual type of superconductivity has been revealed: B _c2(T) curves of the crystals with T _c > 20 K have positive curvature (as in some HTSCs), and those of the crystals with T _c < 15 K described by the usual Werthamer-Helfand-Hohenberg (WHH) formula. The R(T) and X(T) dependences of the crystals with T _c ≈ 32 K and T _c ≈ 11 K in the temperature range T ? T _c are linear (as in HTSCs) and exponential (BCS), respectively. The experimental results are discussed using the extended saddle point model by Abrikosov.     

Functional derivative δTc/δα2 (Ω)F(Ω) for weak coupling superconductors

We present approximate analytic calculation of the functional derivative $\text{δT}{}_{\mathrm{c}}\text{δα}{}^2\text{(Ω)F(Ω)}$, where T_c is the superconducting critical temperature and $\text{α}{}^2\text{(Ω)F(Ω)}$ is the electron-phonon spectral function, within the “square-well model” for the phonon mediated electron-electron interaction and weak coupling limit $\text{ω}{}_{\mathrm{D}}\text{(2πT}{}_{\mathrm{c}}\text{)? 1 (ω}{}_{\mathrm{D}}$ is the Debye energy). It is found that $\text{δT}{}_{\mathrm{c}}\text{δα}{}^2\text{(Ω)F(Ω) = (1 + λ)}{}^{-1}\text{G(Ω)}$ where λ is the familiar electron-phonon coupling parameter and $\text{G(Ω)}$ is a universal function of the reduced frequency $\text{Ω}\text{=}\text{Ω}\text{T}{}_{\mathrm{c}}$. We compare this formula with accurate numerical results for several weak coupling superconductors. The overall agreement is good     

The correlation function for a quantum oscillator in a low-temperature heat bath

The momentum autocorrelation function c(t) for a quantum oscillator coupled with harmonic forces to a heat bath of oscillators is calculated at low temperatures. It is found that c(t) contains two distinct terms: one, the zero-point contribution c₀(t), is temperature independent, and the other, c₁(t), does depend on temperature. We concentrate our attention on the low-temperature case. An expression for c₁(t) is obtained, which is valid for arbitrary strenghts of the coupling and for arbitrary times. It is shown that c₁(t) is governed by the low-frequency behaviour of F(λ) = A²(λ)ϱ(λ), where ϱ(λ) is the density of normal modes and A(λ) is the central-oscillator component of the λth normal mode; other details of the problem are irrelevant. It is found that c₁(t) decays in time as an inverse-power law, with a relaxation time t_q ≈ ħ/kT.     

Operator product expansion coefficients in N = 1 superconformal theory and slightly relevant perturbation

We have computed general four-point functions and obtained the operator-product-expansion coefficients in the discrete N = 1 superconformal theories using the method developed by Dotsenko and Fateev. As an application of our results, we have considered the effect of applying the slightly relevant perturbation on superconformal theories. For large m it is shown that the central charge c(m) shifts twice the minimal possible amount as c(m) → c(m − 2), in accordance with what the Witten index tr(−1)^F suggests.     

Quantum Tomography under Prior Information

We provide a detailed analysis of the question: how many measurement settings or outcomes are needed in order to identify an unknown quantum state which is constrained by prior information? We show that if the prior information restricts the possible states to a set of lower dimensionality, then topological obstructions can increase the required number of outcomes by a factor of two over the number of real parameters needed to characterize the set of all states. Conversely, we show that almost every measurement becomes informationally complete with respect to the constrained set if the number of outcomes exceeds twice the Minkowski dimension of the set. We apply the obtained results to determine the minimal number of outcomes of measurements which are informationally complete with respect to states with rank constraints. In particular, we show that the minimal number of measurement outcomes (POVM elements) necessary to identify all pure states in a d-dimensional Hilbert space is 4d?3?c(d) α(d) for some ${c(d)\in[1,2]}$ and α(d) being the number of ones appearing in the binary expansion of (d?1).