Graph kernels,hierarchical clustering,and network community structure: experiments and comparative analysis

There has been a quickly growing interest in properties of complex networks, such as the small world property, power-law degree distribution, network transitivity, and community structure, which seem to be common to many real world networks. In this study, we consider the community property which is also found in many real networks. Based on the diffusion kernels of networks, a hierarchical clustering approach is proposed to uncover the community structure of different extent of complex networks. We test the method on some networks with known community structures and find that it can detect significant community structure in these networks. Comparison with related methods shows the effectiveness of the method.     

Communities recognition in the Chesapeake Bay ecosystem by dynamical clustering algorithms based on different oscillators systems

We have recently introduced [Phys. Rev. E 75, 045102(R) (2007); AIP Conference Proceedings 965, 2007, p. 323] an efficient method for the detection and identification of modules in complex networks, based on the de-synchronization properties (dynamical clustering) of phase oscillators. In this paper we apply the dynamical clustering tecnique to the identification of communities of marine organisms living in the Chesapeake Bay food web. We show that our algorithm is able to perform a very reliable classification of the real communities existing in this ecosystem by using different kinds of dynamical oscillators. We compare also our results with those of other methods for the detection of community structures in complex networks.     

Modeling network growth with assortative mixing

We propose a model of an underlying mechanism responsible for the formation of assortative mixing in networks between “similar” nodes or vertices based on generic vertex properties. Existing models focus on a particular type of assortative mixing, such as mixing by vertex degree, or present methods of generating a network with certain properties, rather than modeling a mechanism driving assortative mixing during network growth. The motivation is to model assortative mixing by non-topological vertex properties, and the influence of these non-topological properties on network topology. The model is studied in detail for discrete and hierarchical vertex properties, and we use simulations to study the topology of resulting networks. We show that assortative mixing by generic properties directly drives the formation of community structure beyond a threshold assortativity of r ∼0.5, which in turn influences other topological properties. This direct relationship is demonstrated by introducing a new measure to characterise the correlation between assortative mixing and community structure in a network. Additionally, we introduce a novel type of assortative mixing in systems with hierarchical vertex properties, from which a hierarchical community structure is found to result. Electronic supplementary material Supplementary Online Material     

Detection of community structure in networks based on community coefficients

Determining community structure in networks is fundamental to the analysis of the structural and functional properties of those networks, including social networks, computer networks, and biological networks. Modularity function Q$Q$, which was proposed by Newman and Girvan, was once the most widely used criterion for evaluating the partition of a network into communities. However, modularity Q$Q$ is subject to a serious resolution limit. In this paper, we propose a new function for evaluating the partition of a network into communities. This is called community coefficient C$C$. Using community coefficient C$C$, we can automatically identify the ideal number of communities in the network, without any prior knowledge. We demonstrate that community coefficient C$C$ is superior to the modularity Q$Q$ and does not have a resolution limit. We also compared the two widely used community structure partitioning methods, the hierarchical partitioning algorithm and the normalized cuts (Ncut) spectral partitioning algorithm. We tested these methods on computer-generated networks and real-world networks whose community structures were already known. The Ncut algorithm and community coefficient C$C$ were found to produce better results than hierarchical algorithms. Unlike several other community detection methods, the proposed method effectively partitioned the networks into different community structures and indicated the correct number of communities.     

Isotope shifts and hyperfine structure in the transitions of gadolinium

High-resolution resonance ionization mass spectrometry has been used to measure isotope shifts and hyperfine structure in all (J = 2-6) and the transitions of gadolinium (Gd I). Gadolinium atoms in an atomic beam were excited with a tunable single-frequency laser in the wavelength range of 422-429 nm. Resonant excitation was followed by photoionization with the 363.8 nm line of an argon ion laser and resulting ions were mass separated and detected with a quadrupole mass spectrometer. Isotope shifts for all stable gadolinium isotopes in these transitions have been measured for the first time. Additionally, the hyperfine structure constants of the upper states have been derived for the isotopes ^{155, 157} Gd and are compared with previous work. Using prior experimental values for the mean nuclear charge radii, derived from the combination of muonic atoms and electron scattering data, field shift and specific mass shift coefficients for the investigated transitions have been determined and nuclear charge parameters for the minor isotopes ^{152, 154} Gd have been calculated. Received 18 November 1999     

Community structure of complex software systems: Analysis and applications

Due to notable discoveries in the fast evolving field of complex networks, recent research in software engineering has also focused on representing software systems with networks. Previous work has observed that these networks follow scale-free degree distributions and reveal small-world phenomena, while we here explore another property commonly found in different complex networks, i.e. community structure. We adopt class dependency networks, where nodes represent software classes and edges represent dependencies among them, and show that these networks reveal a significant community structure, characterized by similar properties as observed in other complex networks. However, although intuitive and anticipated by different phenomena, identified communities do not exactly correspond to software packages. We empirically confirm our observations on several networks constructed from Java and various third party libraries, and propose different applications of community detection to software engineering.     

Detection of node group membership in networks with group overlap

Most networks found in social and biochemical systems have modular structures. An important question prompted by the modularity of these networks is whether nodes can be said to belong to a single group. If they cannot, we would need to consider the role of “overlapping communities.” Despite some efforts in this direction, the problem of detecting overlapping groups remains unsolved because there is neither a formal definition of overlapping community, nor an ensemble of networks with which to test the performance of group detection algorithms when nodes can belong to more than one group. Here, we introduce an ensemble of networks with overlapping groups. We then apply three group identification methods – modularity maximization, k-clique percolation, and modularity-landscape surveying – to these networks. We find that the modularity-landscape surveying method is the only one able to detect heterogeneities in node memberships, and that those heterogeneities are only detectable when the overlap is small. Surprisingly, we find that the k-clique percolation method is unable to detect node membership for the overlapping case.     

Adjusting from disjoint to overlapping community detection of complex networks

The investigation of community structures is one of the most important problems in the field of complex networks and has countless applications in different disciplines: biology, computer, social sciences, etc. Many community detection algorithms have been developed in various fields recently. The vast majority of these algorithms only find disjoint communities; however, in many real-world networks communities often overlap to some extent. In this paper, we propose an efficient method for adjusting these classical algorithms to match the requirement for discovering overlapping communities in complex networks, which is based on a local definition of community strength. The method can in principle be applied with any clustering algorithm. Tests on a set of computer generated and real-world networks give excellent results. In particular, we show that the method can also allow one to availably analyze the problem of unstable nodes in community detection, which is very helpful for understanding the structural properties of the networks correctly and comprehensively.     

A mathematical programming approach for sequential clustering of dynamic networks

A common analysis performed on dynamic networks is community structure detection, achallenging problem that aims to track the temporal evolution of network modules. Anemerging area in this field is evolutionary clustering, where thecommunity structure of a network snapshot is identified by taking into account both itscurrent state as well as previous time points. Based on this concept, we have developed amixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusterseach snapshot of a dynamic network. The modularity metric is used to determine the qualityof community structure of the current snapshot and the historical cost is accounted for byoptimising the number of node pairs co-clustered at the previous time point that remain soin the current snapshot partition. Our method is tested on social networks of interactionsamong high school students, college students and members of the Brazilian Congress. Weshow that, for an adequate parameter setting, our algorithm detects the classes that thesestudents belong more accurately than partitioning each time step individually or bypartitioning the aggregated snapshots. Our method also detects drastic discontinuities ininteraction patterns across network snapshots. Finally, we present comparative resultswith similar community detection methods for time-dependent networks from the literature.Overall, we illustrate the applicability of mathematical programming as a flexible,adaptable and systematic approach for these community detection problems.     

Preservation of network degree distributions from non-uniform failures

There has been a considerable amount of interest in recent years on the robustness of networks to failures. Many previous studies have concentrated on the effects of node and edge removals on the connectivity structure of a static network; the networks are considered to be static in the sense that no compensatory measures are allowed for recovery of the original structure. Real world networks such as the world wide web, however, are not static and experience a considerable amount of turnover, where nodes and edges are both added and deleted. Considering degree-based node removals, we examine the possibility of preserving networks from these types of disruptions. We recover the original degree distribution by allowing the network to react to the attack by introducing new nodes and attaching their edges via specially tailored schemes. We focus particularly on the case of non-uniform failures, a subject that has received little attention in the context of evolving networks. Using a combination of analytical techniques and numerical simulations, we demonstrate how to preserve the exact degree distribution of the studied networks from various forms of attack.     

Random field Ising model and community structure in complex networks

We propose a method to determine the community structure of a complex network. In this method the ground state problem of a ferromagnetic random field Ising model is considered on the network with the magnetic field B_s = +∞, B_t = -∞, and B_i≠s,t=0 for a node pair s and t. The ground state problem is equivalent to the so-called maximum flow problem, which can be solved exactly numerically with the help of a combinatorial optimization algorithm. The community structure is then identified from the ground state Ising spin domains for all pairs of s and t. Our method provides a criterion for the existence of the community structure, and is applicable equally well to unweighted and weighted networks. We demonstrate the performance of the method by applying it to the Barabási-Albert network, Zachary karate club network, the scientific collaboration network, and the stock price correlation network. (Ising, Potts, etc.)     

Some exact results on the ultrametric overlap distribution in mean field spin glass models (I)

The mean field spin glass model is analyzed by a combination of exact methods and a simple Ansatz. The method exploited is general, and can be applied to others disordered mean field models such as, e.g., neural networks. It is well known that the probability measure of overlaps among replicas carries the whole physical content of these models. A functional order parameter of Parisi type is introduced by rigorous methods, according to previous works by F. Guerra. By the Ansatz that the functional order parameter is the correct order parameter of the model, we explicitly find the full overlap distribution. The physical interpretation of the functional order parameter is obtained, and ultrametricity of overlaps is derived as a natural consequence of a branching diffusion process. It is shown by explicit construction that ultrametricity of the 3-replicas overlap distribution together with the Ghirlanda-Guerra relations determines the distribution of overlaps among s replicas, for any s, in terms of the one-overlap distribution. Received 14 February 2000     

Ground state energy of N Frenkel excitons

By using the composite many-body theory for Frenkel excitons we have recently developed, we here derive the ground state energy of N Frenkel excitons in the Born approximation through the Hamiltonian mean value in a state made of N identical Q = 0 excitons. While this quantity reads as a density expansion in the case of Wannier excitons, due to many-body effects induced by fermion exchanges between N composite particles, we show that the Hamiltonian mean value for N Frenkel excitons only contains a first order term in density, just as for elementary bosons. Such a simple result comes from a subtle balance, difficult to guess a priori, between fermion exchanges for two or more Frenkel excitons appearing in Coulomb term and the ones appearing in the N exciton normalization factor – the cancellation being exact within terms in 1/N_s where N_s is the number of atomic sites in the sample. This result could make us naively believe that, due to the tight binding approximation on which Frenkel excitons are based, these excitons are just bare elementary bosons while their composite nature definitely appears at various stages in the precise calculation of the Hamiltonian mean value.     

Community structure in the United States House of Representatives

We investigate the networks of committee and subcommittee assignments in the United States House of Representatives from the 101st-108th Congresses, with the committees connected by “interlocks” or common membership. We examine the community structure in these networks using several methods, revealing strong links between certain committees as well as an intrinsic hierarchical structure in the House as a whole. We identify structural changes, including additional hierarchical levels and higher modularity, resulting from the 1994 election, in which the Republican party earned majority status in the House for the first time in more than 40 years. We also combine our network approach with the analysis of roll call votes using singular value decomposition to uncover correlations between the political and organizational structure of House committees.     

Interpersonal interactions and human dynamics in a large social network

We study a large social network consisting of over 10⁶ individuals, who form an Internet community and organize themselves in groups of different sizes. On the basis of the users’ list of friends and other data registered in the database we investigate the structure and time development of the network. The structure of this friendship network is very similar to the structure of different social networks. However, here a degree distribution exhibiting two scaling regimes, power-law for low connectivity and exponential for large connectivity, was found. The groups size distribution and distribution of number of groups of an individual have power-law form. We found very interesting scaling laws concerning human dynamics. Our research has shown how long people are interested in a single task.     

Large-scale structure of time evolving citation networks

In this paper we examine a number of methods for probing and understanding the large-scale structure of networks that evolve over time. We focus in particular on citation networks, networks of references between documents such as papers, patents, or court cases. We describe three different methods of analysis, one based on an expectation-maximization algorithm, one based on modularity optimization, and one based on eigenvector centrality. Using the network of citations between opinions of the United States Supreme Court as an example, we demonstrate how each of these methods can reveal significant structural divisions in the network and how, ultimately, the combination of all three can help us develop a coherent overall picture of the network's shape.     

Force chain splitting in granular materials: A mechanism for large-scale pseudo-elastic behaviour

We investigate both numerically and analytically the effect of strong disorder on the large-scale properties of the hyperbolic equations for stresses proposed in J.-P. Bouchaud, M.E. Cates, P. Claudin, J. Phys. I 5, 639 (1995), and J.P. Wittmer, P. Claudin, M.E. Cates, J.-P. Bouchaud, Nature 382, 336 (1996); J.P. Wittmer, P. Claudin, M.E. Cates, J. Phys. I 7, 39 (1997). The physical mechanism that we model is the local splitting of the force chains (the characteristics of the hyperbolic equation) by packing defects. In analogy with the theory of light diffusion in a turbid medium, we propose a Boltzmann-like equation to describe these processes. We show that, for isotropic packings, the resulting large-scale effective equations for the stresses have exactly the same structure as those of an elastic body, despite the fact that no displacement field needs to be introduced at all. Correspondingly, the response function evolves from a two-peak structure at short scales to a broad hump at large scales. We find, however, that the Poisson ratio is anomalously large and incompatible with classical elasticity theory that requires the reference state to be thermodynamically stable. Received 13 November 2000 and Received in final form 3 January 2001     

Some exact results on the ultrametric overlap distribution in mean field spin glass models (I)

The mean field spin glass model is analyzed by a combination of exact methods and a powerful Ansatz. The method exploited is general, and can be applied to others disordered mean field models such as, e.g., neural networks.It is well known that the probability measure of overlaps among replicas carries the whole physical content of these models. A functional order parameter of Parisi type is introduced by rigorous methods, according to previous works by F. Guerra. By the Ansatz that the functional order parameter is the correct order parameter of the model, we explicitly find the full overlap distribution. The physical interpretation of the functional order parameter is obtained, and ultrametricity of overlaps is derived as a natural consequence of a branching diffusion process.It is shown by explicit construction that ultrametricity of the 3-replicas overlap distribution together with the Ghirlanda-Guerra relations determines the distribution of overlaps among s replicas, for any s, in terms of the one-overlap distribution.     

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.     

Graph spectra and the detectability of community structure in networks

We study networks that display community structure--groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods, we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.