Search

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.

Biological networks provide great potential to understand how cells function. Network motifs, frequent topological patterns, are key structures through which biological networks operate. Counting independent (i.e. non-overlapping) copies of a given motif however remains to be a computationally hard problem. Motif counting problem becomes computationally even harder for biological networks as biological interactions are uncertain events. The central challenge behind this problem is that different embeddings of a given motif in a network can share edges. Such edges can create complex computational dependencies between different instances of the given motif. In this paper, we develop a novel algorithm for counting independent copies of a given motif topology in probabilistic biological networks. We propose a novel mathematical model to capture the dependency between each embedding and all the other embeddings, which it overlaps with. We prove the correctness of this model. Our experiments on real and synthetic networks demonstrate that our method counts non-overlapping embeddings in practical time for a broad range of networks with different probability, and topology models as well as reasonable range of network sizes.

The small world phenomenon, Milgram (1967) has inspired the study of real networks such as cellular networks, telephone call networks, citation networks, power and neural networks, etc. The present work is about the study of the graphs produced by efficient solutions of the bi-objective {0,1}-knapsack problem. The experiments show that these graphs exhibit properties of small world networks. The importance of the supported and non-supported solutions in the entire efficient graph is investigated. The present research could be useful for developing more effective search strategies in both exact and approximate solution methods of {0,1} multi-objective combinatorial optimization problems.

Essence is a formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. Essence provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. Essence also allows these combinatorial objects to be nested to arbitrary depth, providing for example sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be specified directly by using a decision variable whose type is precisely that combinatorial object.

A coupled cell network is a finite directed graph in which nodes and edges are classified into equivalence classes. Such networks arise in a formal theory of coupled systems of differential equations, as a schematic indication of the topology of the coupling, but they can be studied independently as combinatorial objects. The edges of a coupled cell network are "identical" if they are all equivalent, and the network is "homogeneous" if all nodes have isomorphic sets of input edges. Golubitsky et al. [2005] proved that every homogeneous identical-edge coupled cell network is a quotient of a network that has no multiple edges and no self-connections. We generalize this theorem to any coupled cell network by removing the conditions of homogeneity and identical edges. The problem is a purely combinatorial assertion about labeled directed graphs, and we give two combinatorial proofs. Both proofs eliminate self-connections inductively. The first proof also eliminates multiple edges inductively, the main feature being the specification of the inductive step in terms of a complexity measure. The second proof obtains a more efficient result by eliminating all multiple edges in a single construction.

Many real networks, including those in social, technological, and biological realms, are small-world networks. The two distinguishing characteristics of small-world networks are high local clustering and small average internode distance. A great deal of previous research on small-world networks has been based on probabilistic methods, with a rather small number of researchers advocating deterministic models. In this paper, we further the study of deterministic small-world networks and show that Cayley graphs may be good models for such networks. Small-world networks based on Cayley graphs possess simple structures and significant adaptability. The Cayley-graph model has pedagogical value and can also be used for designing and analyzing communication and the other real networks.

The network synthesis problem introduced by Gomory and Hu is to construct a network with capacities on the edges so that the maximum flow between every pair of nodes (taken nonsimultaneously) exceeds certain given flow requirements and such that the total capacity on the edges is minimum. In some applications, edges have a certain setup cost associated with them, and it is of interest to design the network with as few edges as possible. This variant of the network synthesis problem was studied by Gusfield, who gave two algorithms that build networks with the number of edges less than or equal to those in the networks constructed by Gomory and Hu's algorithm. In this paper, we give a new algorithm for this variant of the network synthesis problem. Our algorithm is guaranteed to use, at most, the number of edges as in the networks of Gusfield's algorithms. We also give a lower bound on the number of edges required in any solution to the network synthesis problem. Recently, Sridhar and Chandrasekaran gave a polynomial-time algorithm that solves the integer network synthesis problem. We give a modification of our network synthesis algorithm that solves the integer version of the problem with an objective of using few edges.

Over the past few decades, network science has introduced several statistical measures to determine the topological structure of large networks. Initially, the focus was on binary networks, where edges are either present or not. Thus, many of the earlier measures can only be applied to binary networks and not to weighted networks. More recently, it has been shown that weighted networks have a rich structure, and several generalized measures have been introduced. We use persistent homology, a recent technique from computational topology, to analyse four weighted collaboration networks. We include the first and second Betti numbers for the first time for this type of analysis. We show that persistent homology corresponds to tangible features of the networks. Furthermore, we use it to distinguish the collaboration networks from similar random networks.

This paper considers the integral multicommodity o w problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider 3-stage networks. Using existing results on (g; f)-factors of bipartite graphs, we show sufcient and necessary conditions for the existence of a solution when the network has at most 2 secondary switches. In contrast, the problem is shown to be NP-complete if the network has 3 or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binary n-cube, and the generalized cube network) as a proper subset. Networks in the new class may have arbitrary number of stages, moreover, each stage may contain identical switches of any arbitrary size. The notion of extra-stage networks is extended to the new class, and the problem is shown to have polynomial time solutions on r-stage networks where r = 3, or r 3 and each link has a unit capacity. The latter result implies an efcient algorithm for deciding admissible permutations on conventional extra-stage hypercubic networks. In contrast, we show that the multicommodity o w problem is NP-complete on extra-stage networks, even if r = 6, each link has an integral capacity 3, and all o w demands are equal.

Across the sciences, the statistical analysis of networks is central to the production of knowledge on relational phenomena. Because of their ability to model the structural generation of networks based on both endogenous and exogenous factors, exponential random graph models are a ubiquitous means of analysis. However, they are limited by an inability to model networks with valued edges. We address this problem by introducing a class of generalized exponential random graph models capable of modeling networks whose edges have continuous values (bounded or unbounded), thus greatly expanding the scope of networks applied researchers can subject to statistical analysis.

International audience; In this work we present a new methodology to study the structure of the configuration spaces of hard combinatorial problems. It consists in building the network that has as nodes the locally optimal configurations and as edges the weighted oriented transitions between their basins of attraction. We apply the approach to the detection of communities in the optima networks produced by two different classes of instances of a hard combinatorial optimization problem: the quadratic assignment problem (QAP). We provide evidence indicating that the two problem instance classes give rise to very different configuration spaces. For the so-called real-like class, the networks possess a clear modular structure, while the optima networks belonging to the class of random uniform instances are less well partitionable into clusters. This is convincingly supported by using several statistical tests. Finally, we shortly discuss the consequences of the findings for heuristically searching the corresponding problem spaces.

Complex data can often be represented in terms of random graphs or networks. Important features of real world networks can be described by a special class of random graphs called small-world networks. Small-world networks emerge in many contexts, from systems biology to distributed technological systems. Here we ask how the functional and structural properties of specialized real world networks are reflected in convergence-divergence properties of their edges and nodes. We introduced a novel metric called edge convergence degree and studied it on small-world networks generated according to different rules. The obtained results were compared with Erdős-Renyi random networks. We found that convergence degree sensitively distinguishes different models of random networks we studied.

It is required to interconnect n existing networks in the plane by new links of minimal total length. We assume that the edges of the networks are straight and that it is possible to make connections along the edges or to the vertices. The use o f Steiner points is also allowed. Though the theoretical number of solutions to the problem is uncountable, we prove that it is enough to consider a finite set of locally optimal solutions with a limit on the number of connections along edges. This makes it possible to solve the problem in finite time by methods similar to those used for the Euclidean Steiner tree problem. The problem can be generalized to include flow-dependent costs for the various links.

Detecting community structure in biological and social networks recently attracts increasing attention in various fields including mathematics, physics and biology. Identifying communities in complex networks can help us to understand and exploit the networks more clearly and efficiently. In this paper, we introduced a method based on a combinatorial optimization problem -- traveling salesman problem (TSP) as optimal rearrangement clustering for finding community structure in complex networks. This method can explore the global topology of a network and thus is effective in detecting modularity structure. Unlike most other algorithms for community identification, an advantage of this method is that it does not need to spend much time in finding a proper k, the number of communities in a network. We applied this method to several widely well-studied networks including a protein-protein interaction network, which demonstrates that this method is effective in detecting meaningful communities or functional modules.

Non-isomorphic coupled cell networks with the same number of cells and with equivalent dynamics are said to be ODEequivalent. Moreover, they are all related by a linear algebra condition involving their graph adjacency matrices. A network in an ODE-class is said to be minimal if it has a minimum number of edges among all the networks of the class. In this short paper we review the characterization of the minimal networks of an ODE-equivalence class and we present an example for the case of non-homogeneous networks. Networks of nonlinear dynamical systems model many real world problems. See for example Stewart[4] and references therein. Mathematically, a coupled cell network can be idealised as a directed graph representing schematically a set of dynamical systems (the cells) that are coupled together, and the couplings (the edges) among them. Following the theory of Stewart etal [5] and Golubitsky etal [3], we associate to each coupled cell network a class of ordinary differential equations (ODEs) compatible with the structure of the network – the class of coupled cell systems. Non-isomorphic coupled cell networks can have equivalent dynamics. Such networks are said to be ODE-equivalent [3]. Dias and Stewart [2] prove that up to re-numeration of cells, two coupled cell networks are ODE-equivalent if and only if the set of all corresponding linear vector fields coincide. Moreover, cells can be assumed to be one-dimensional for that purpose. In [1] we compare ODE-equivalent coupled cell networks in terms of the number of edges. A network in an ODEequivalence class is said to be minimal if it has a minimum number of edges.

7 pages, 6 figures., We analyze a model that interpolates between scale-free and Erdos-Rényi networks. The model introduced generates a one-parameter family of networks and allows one to analyze the role of structural heterogeneity. Analytical calculations are compared with extensive numerical simulations in order to describe the transition between these two important classes of networks. Finally, an application of the proposed model to the study of the percolation transition is presented., J.G.-G. acknowledges financial support of the MEC through a FPU grant. Y.M. was supported by MEC through the Ramón y Cajal Program. This work has been partially supported by Spanish DGICYT, Project Nos. FIS2004-05073-C04-01 and FIS2005-00337.

Non-recursive and explicit expressions for calculating the number of ways to distribute n indistinguishable balls into m distinguishable bins with different capacities have been derived. Similar expression for the special case where bins have the same capacity was previously reported in the literature. Theses expressions can be used to study network graphs with grid structures. In this line, we have derived some topological properties of meshes, furnishing some expressions to calculate the surface area and volume of radial spheres in the mesh network.

We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbe and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877, 2000). In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem is strongly NP-complete for any fixed K, and we derive a new class of facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem.

We introduce the following combinatorial optimization problem: Given a connected graph G, find a spanning tree T of G with the smallest number of branchv ertices (vertices of degree 3 or more in T). The problem is motivated by new technologies in the realm of optical networks. We investigate algorithmic and combinatorial aspects of the problem.

During the Summers of 1991 and 1992 the principal investigator research the use of combinatorial techniques in analyzing problems involving the repair of K-terminal networks, which are networks given with a distinguished subset K of the vortex-set. (Ordinary graph theory can be viewed as being equivalent to the special case K=V(G).) There are large bodies of existing literature describing the uses of such techniques in analyzing (1) ordinary networks (for which the reliability and repair problems are very similar to each other, being connected with certain matroids associated to the network) and (2) K-terminal reliability problems; the fundamental problem is to find out how these two bodies of material generalize to the repair of K-terminal networks. The original proposal listed several specific areas of research, of which the second and fifth turned out to be the most interesting.

The problem of calculating the combinatorial power of certain SW-banyan networks is related to a problem of enumerating certain matrices. Examples of two- and three-stage networks are used to demonstrate the technique. In each case, a polynomial-time algorithm is found to solve the problem. The results are presented for each case and certain asymptotic behavior is noted. >

This short note is an application of some theorems of graph theory to the problem of the minimum number of counter-examples needed to show that a special class of theories is complete.

The correspondence presents three classes of cube-connected networks with individual stage control based on a group theoretic modeling of interconnection networks. It is shown that these classes of networks retain nonisomorphic groups of permutations. Although the permutations realizable by such networks are rather limited in number, the simplicity of their control scheme makes them attractive. Moreover, the interconnection power of these networks can be enhanced by simulating the networks which belong to one class by any member of that class.

The definition of ordinary electric networks is based on graphs. Since such a formulation is inadequate in many respects, we define a new network concept, namely, a generalized network, which is a network based on a matroid. To make the paper self-contained an introduction to basic matroid theory is given in the first part of the paper. We then define a generalized network and formulate the network analysis and network synthesis problems for generalized networks. A number of new results are obtained for both analysis and synthesis and some old results for networks on graphs are generalized to networks on matroids. It is shown that the principle of duality, which does not hold for networks on graphs but is valid for generalized networks, adds power and insight for solving analysis and synthesis problems. The analysis problem, though formulated in terms of resistance networks, holds for networks containing all types of elements. The synthesis problem that is treated is the crucial one of the realization of a p-port resistance network.

In connection with a previous paper, an expression is derived for the number of possibilities in whichn distinguishable elements can be distributed intom≤n classes, so that each class contains at least one element.

A well-known consequence of the König theorem on maximum matchings and minimum covers in bipartite graphs (5) or of the P. Hall theorem on systems of distinct representatives for sets (4) asserts that an n by n (0, 1)-matrix A having precisely p ones in each row and column can be written as a sum of p permutation matrices:Our main objective is a generalization of (1.1) along the following lines. Let A be an arbitrary m by n (0, 1)-matrix. Call an m by n (0, 1)-matrix P a permutation matrix if PPT = I, where PT is the transpose of P and I is the identity matrix of order m.