A note on the Estrada-Hatano communicability algorithm for detecting community structure in complex networks

Recently Estrada and Hatano proposed an algorithm for the detection of community structure in complex networks using the concept of network communicability. Here we amend this algorithm by eliminating the subjectivity of choosing degree of overlapping and including an additional check of the fitness of detected communities. We show that this amendment can detect some communities which remain undetected by Estrada and Hatano’s algorithm. For instance, let G(p, q) be a graph obtained from two cliques, K_p and K_q(p ? q ? 3), joined by a single edge. It is apparent that this graph contains two communities, namely the two cliques. However, Estrada and Hatano’s algorithm detects only K_q as a community when p is sufficiently larger than q. Our algorithm correctly detects both communities. Also, our method also finds the correct community structure in one of the classic benchmark networks, the Zachary karate club.     

The graph coloring problem: A neuronal network approach

Solution of an optimization problem with linear constraints through the continuous Hopfield network (CHN) is based on an energy or Lyapunov function that decreases as the system evolves until a local minimum value is attained. This approach is extended in to optimization problems with quadratic constraints. As a particular case, the graph coloring problem (GCP) is analyzed. The mapping procedure and an appropriate parameter-setting procedure are detailed. To test the theoretical results, some computational experiments solving the GCP are shown.     

Local estimates for eigenvector-like centralities of complex networks

We will analyze several centrality measures by giving a general framework that includes the Bonacich centrality, PageRank centrality or in-degree vector, among others. We will get some local scale estimators for such global measures by giving some geometrical characterizations and some deviation results that help to quantify the error of approximating a spectral centrality by a local estimator.     

Bisecting a 4-connected graph with three resource sets

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T₁,T₂,…,T_k of nodes, called resource sets, where |T_i| is even for each i. The partition problem with k resource sets asks to find a partition V₁ and V₂ of the node set V such that the graphs induced by V₁ and V₂ are both connected and |V₁∩T_i|=|V₂∩T_i|=|T_i|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k?3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K₄ as its subgraph, then a bisection exists and it can be found in O(|V|³log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.     

Robust global synchronization of complex networks with neutral-type delayed nodes

In this paper, the problems of robust global exponential synchronization for a class of complex networks with time-varying delayed couplings are considered. Each node in the network is composed of a class of delayed neural networks described by a nonlinear delay differential equation of neutral-type. Since model errors commonly exist in practical applications, the parameter uncertainties are involved in the considered model. Sufficient conditions that ensure the complex networks to be robustly globally exponentially synchronized are obtained by using the Lyapunov functional method and some properties of Kronecker product. An illustrative example is presented to show the effectiveness of the proposed approach.     

Observer-based lag synchronization between two different complex networks

In this paper, some new criteria for lag synchronization between two or more complex networks are proposed based on the theory of state observer. Some adaptive controllers are designed to make the drive and response systems achieve lag synchronization, no matter whether the nodes in the two systems are with the same dynamical character or the coupling configuration matrices are nonidentical. In addition, based on the output coupling, the amount of coupling variables between two connected nodes is flexible, which can save a lot of channel resources, simplify the network topology and has more significant meanings in engineering applications. At last, the effects of the lag synchronization criteria are verified through some simulation experiments.     

Bipartite and directed scale-free complex networks arising from zeta functions

We construct a new class of directed and bipartite random graphs whose topology is governed by the analytic properties of multiple zeta functions. The bipartite L-graphs and the multiplicative zeta graphs are relevant examples of the proposed construction. Phase transitions and percolation thresholds for our models are determined.     

The neighborhood complex of a random graph

For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well-known result of Lovász that if ‖N[G]‖ is k-connected, then the chromatic number of G is at least k+3.We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(logd), compared to the expected dimension d of the complex itself.     

A preferential attachment model with Poisson growth for scale-free networks

We propose a scale-free network model with a tunable power-law exponent. The Poisson growth model, as we call it, is an offshoot of the celebrated model of Barabási and Albert where a network is generated iteratively from a small seed network; at each step a node is added together with a number of incident edges preferentially attached to nodes already in the network. A key feature of our model is that the number of edges added at each step is a random variable with Poisson distribution, and, unlike the Barabási–Albert model where this quantity is fixed, it can generate any network. Our model is motivated by an application in Bayesian inference implemented as Markov chain Monte Carlo to estimate a network; for this purpose, we also give a formula for the probability of a network under our model.     

Symmetry in complex networks

We consider the size and structure of the automorphism groups of a variety of empirical ‘real-world’ networks and find that, in contrast to classical random graph models, many real-world networks are richly symmetric. We construct a practical network automorphism group decomposition, relate automorphism group structure to network topology and discuss generic forms of symmetry and their origin in real-world networks. We also comment on how symmetry can affect network redundancy and robustness.     

Synchronization criterions and pinning control of general complex networks with time delay

The problems of synchronization and pinning control for general time-delay complex dynamical networks are investigated. In this paper, less conservative criterions for both continuous-time and discrete-time complex dynamical networks with time delay are obtained. Pinning control strategies are respectively, designed to make these complex dynamical networks synchronized. Moreover, the problems of designing controllers are converted into solving optimal problems of a series of linear matrix inequalities, which reduces the computation complexity. Finally, numerical simulations verify the effectiveness of our methodology.     

Adaptive synchronization of two nonlinearly coupled complex dynamical networks with delayed coupling

This paper investigates the adaptive synchronization between two nonlinearly delay-coupled complex networks with the bidirectional actions and nonidentical topological structures. Based on LaSalle’s invariance principle, some criteria for the synchronization between two coupled complex networks are achieved via adaptive control. To validate the proposed methods, the unified chaotic system as the nodes of the networks are analyzed in detail, and numerical simulations are given to illustrate the theoretical results.     

Upper bounds for the forwarding indices of communication networks

The decision version of the forwarding index problem is, given a connected graph G and an integer ξ, to find a way of connecting each ordered pair of vertices by a path so that every vertex is an internal point of at most such paths. The optimization version of the problem is to find the smallest ξ for which a routing of this kind exists. Such a problem arises in the design of communication networks and distributed architectures. A model of parallel computation is represented by a network of processors, or machines processing and forwarding (synchronous) messages to each other, subject to physical constraints bearing on either the number of messages that can be processed by a single machine or the number of messages that can be sent through a connection. It was in this context that the problem was first introduced by Chung et al. (IEEE Trans. Inform. Theory 33 (1987) 224). The aim of this paper is to establish upper bounds for the optimal ξ as a function of the connectivity of the graph.     

Graphs for small multiprocessor interconnection networks

Let D be the diameter of a graph G and let λ₁ be the largest eigenvalue of its (0, 1)-adjacency matrix. We give a proof of the fact that there are exactly 69 non-trivial connected graphs with (D + 1)λ₁ ? 9. These 69 graphs all have up to 10 vertices and were recently found to be suitable models for small multiprocessor interconnection networks. We also examine the suitability of integral graphs to model multiprocessor interconnection networks, especially with respect to the load balancing problem. In addition, we classify integral graphs with small values of (D + 1)λ₁ in connection with the load balancing problem for multiprocessor systems.