Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

The Tutte polynomial of an infinite family of outerplanar,small-world and self-similar graphs

In this paper we recursively describe the Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs. In particular, we study the Abelian Sandpile Model on these graphs and obtain the generating function of the recurrent configurations. Further, we give some exact analytical expression for the Tutte polynomial at several special points     

The number of spanning trees of an infinite family of outerplanar,small-world and self-similar graphs

In this paper we give an exact analytical expression for the number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. This number is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion properties. The calculation of the number of spanning trees is a demanding and difficult task, in particular for large graphs, and thus there is much interest in obtaining closed expressions for relevant infinite graph families. We have also calculated the spanning tree entropy of the graphs which we have compared with those for graphs with the same average degree.     

A novel configuration model for random graphs with given degree sequence

Recently, random graphs in which vertices are characterized by hidden variables controlling the establishment of edges between pairs of vertices have attracted much attention. This paper presents a specific realization of a class of random network models in which the connection probability between two vertices (i,j) is a specific function of degrees ki and kj. In the framework of the configuration model of random graphs, we find the analytical expressions for the degree correlation and clustering as a function of the variance of the desired degree distribution. The obtained expressions are checked by means of numerical simulations. Possible applications of our model are discussed.     

Market Choices Driven by Reference Groups: A Comparison of Analytical and Simulation Results on Random Networks

The present paper reports simulation results for a simple model of reference group influence on market choices, e.g., brand selection. The model was simulated on three types of random graphs, Erdos–Renyi, Barabasi–Albert, and Watts–Strogatz. The estimates of equilibria based on the simulation results were compared to the equilibria of the theoretical model. It was verified that the simulations exhibited the same qualitative behavior as the theoretical model, and for graphs with high connectivity and low clustering, the quantitative predictions offered a viable approximation. These results allowed extending the results from the simple theoretical model to networks. Thus, by increasing the positive response towards the reference group, the third party may create a bistable situation with two equilibria at which respective brands dominate the market. This task is easier for large reference groups.     

Formulas for the characteristic polynomial coefficients of the pendant graphs of linear chains,cycles and stars

Formulas for the characteristic polynomial (CP) coefficients of three classes of (n + p)-vertex graphs, i.e. linear chains, cycles and stars where p pendant vertices are attached to n base vertices in one-to-one correspondence (p = 0, 1, 2, …, n), have been developed. Such pendant graphs become reciprocal graphs for linear chains and cycles if p = n. The n-vertex star graphs follow the same rule as paths and cycles, they become reciprocal on adding a pendant vertex to each of n vertices. The formulas so developed have been expressed in matrix product and in analytical forms for the three classes of graphs that require only the values of n and p for calculation of the respective CP coefficients. Such formulas have the general applicability for a large variety of molecular graphs with varying n and p and have been shown to be reduced to the corresponding formulas for reciprocal graphs that are the special cases of the graphs discussed here.     

The effects of degree correlations on network topologies and robustness

Complex networks have been applied to model numerous interactive nonlinear systems in the real world. Knowledge about network topology is crucial to an understanding of the function, performance and evolution of complex systems. In the last few years, many network metrics and models have been proposed to investigate the network topology, dynamics and evolution. Since these network metrics and models are derived from a wide range of studies, a systematic study is required to investigate the correlations among them. The present paper explores the effect of degree correlation on the other network metrics through studying an ensemble of graphs where the degree sequence (set of degrees) is fixed. We show that to some extent, the characteristic path length, clustering coefficient, modular extent and robustness of networks are directly influenced by the degree correlation.     

Families of Line-Graphs and Their Quantization

Any directed graph G with N vertices and J edges has an associated line-graph L(G) where the J edges form the vertices of L(G). We show that the non-zero eigenvalues of the adjacency matrices are the same for all graphs of such a family L ⁿ (G). We give necessary and sufficient conditions for a line-graph to be quantisable and demonstrate that the spectra of associated quantum propagators follow the predictions of random matrices under very general conditions. Line-graphs may therefore serve as models to study the semiclassical limit (of large matrix size) of a quantum dynamics on graphs with fixed classical behaviour.     

Insertion and Elimination Lie Algebra: The Ladder Case

We prove that the insertion-elimination Lie algebra of Feynman graphs in the ladder case has a natural interpretation in terms of a certain algebra of infinite dimensional matrices. We study some aspects of its representation theory and we will discuss some relations with the representation of the Heisenberg algebra.     

The statistics of random directed graphs

The analysis of random graphs developed by the author, principally as a model for polymerization processes, is extended to the case of directed random graphs, with models of neural nets in mind. The principal novelty of the directed case is the representation of the partition function by a complex rather than a real integral, and the replacement of simple maxima in asymptotic evaluations by an interesting form of saddle point.     

Minimum Spanning vs. Principal Trees for Structured Approximations of Multi-Dimensional Datasets

Construction of graph-based approximations for multi-dimensional data point clouds is widely used in a variety of areas. Notable examples of applications of such approximators are cellular trajectory inference in single-cell data analysis, analysis of clinical trajectories from synchronic datasets, and skeletonization of images. Several methods have been proposed to construct such approximating graphs, with some based on computation of minimum spanning trees and some based on principal graphs generalizing principal curves. In this article we propose a methodology to compare and benchmark these two graph-based data approximation approaches, as well as to define their hyperparameters. The main idea is to avoid comparing graphs directly, but at first to induce clustering of the data point cloud from the graph approximation and, secondly, to use well-established methods to compare and score the data cloud partitioning induced by the graphs. In particular, mutual information-based approaches prove to be useful in this context. The induced clustering is based on decomposing a graph into non-branching segments, and then clustering the data point cloud by the nearest segment. Such a method allows efficient comparison of graph-based data approximations of arbitrary topology and complexity. The method is implemented in Python using the standard scikit-learn library which provides high speed and efficiency. As a demonstration of the methodology we analyse and compare graph-based data approximation methods using synthetic as well as real-life single cell datasets.     

Clustering and community detection in directed networks: A survey

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed — in the sense that there is directionality on the edges, making the semantics of the edges nonsymmetric as the source node transmits some property to the target one but not vice versa. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of relevant application domains. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs — with clustering being the primary method sought and the primary tool for community detection and evaluation. The goal of this paper is to offer an in-depth comparative review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.     

Symmetry-adapted linear combinations for the eigenvalues and eigenvectors of reciprocal graphs

ABSTRACT

Three classes of reciprocal graphs, viz. monocycle (G^C_n), linear chain (G^L_n) and star (G^K_n) with reciprocal pairs of eigenvalues (λ, 1/λ), are well known. Reciprocal graphs of monocycle (G^C_n) and linear chain (G^L_n) are obtained by putting a pendant vertex to each vertex of simple monocycle (C_n) and simple linear chain (L_n), respectively. A star graph of such kind is obtained by attaching a pendant vertex to the central vertex and to each of the (n ? 1) peripheral vertices of the star graph (K_{1, (n?1)}). An n-fold rotational axis of symmetry for G^C_n and (n ? 1)-fold rotational axis of symmetry for G^K_n have been exploited for obtaining their respective condensed graphs. The condensed graph for G^L_n has been generated from that of G^C_n incorporating proper boundary conditions. Condensed graphs are lower dimensional graphs and are capable of keeping all eigeninformation in condensed form. Thus the eigensolutions (i.e. the eigenvalues and the eigenvectors) in analytical forms for such graphs are obtained by solving 2 × 2 or 4 × 4 determinants that in turn result in the charge densities and bond orders of the corresponding molecules in analytical forms. Some mathematical properties of the eigenvalues of such graphs have also been explored.     

The Number of Large Graphs with a Positive Density of Triangles

We give upper and lower bounds on the number of graphs of fixed degree which have a positive density of triangles. In particular, we show that there are very few such graphs, when compared to the number of graphs without this restriction. We also show that in this case the triangles seem to cluster even at low density.     

Percolation in self-similar networks

We provide a simple proof that graphs in a general class of self-similar networks have zero percolation threshold. The considered self-similar networks include random scale-free graphs with given expected node degrees and zero clustering, scale-free graphs with finite clustering and metric structure, growing scale-free networks, and many real networks. The proof and the derivation of the giant component size do not require the assumption that networks are treelike. Our results rely only on the observation that self-similar networks possess a hierarchy of nested subgraphs whose average degree grows with their depth in the hierarchy. We conjecture that this property is pivotal for percolation in networks.     

Sharpness of the Phase Transition and Exponential Decay of the Subcritical Cluster Size for Percolation on Quasi-Transitive Graphs

We study homogeneous, independent percolation on general quasi-transitive graphs. We prove that in the disorder regime where all clusters are finite almost surely, in fact the expectation of the cluster size is finite. This extends a well-known theorem by Menshikov and Aizenman & Barsky to all quasi-transitive graphs. Moreover we deduce that in this disorder regime the cluster size distribution decays exponentially, extending a result of Aizenman & Newman. Our results apply to both edge and site percolation, as well as long range (edge) percolation. The proof is based on a modification of the Aizenman & Barsky method.     

Factorizations of Polynomials over Noncommutative Algebras and Sufficient Sets of Edges in Directed Graphs

To directed graphs with unique sink and source we associate a noncommutative associative algebra and a polynomial over this algebra. Edges of the graph correspond to pseudo-roots of the polynomial. We give a sufficient condition when coefficients of the polynomial can be rationally expressed via elements of a given set of pseudo-roots (edges). Our results are based on a new theorem for directed graphs also proved in this paper. To the memory of Felix Alexandrovich Berezin. Vladimir Retakh was partially supported by NSA     

Sensing Enhancement on Social Networks: The Role of Network Topology

Sensing and processing information from dynamically changing environments is essential for the survival of animal collectives and the functioning of human society. In this context, previous work has shown that communication between networked agents with some preference towards adopting the majority opinion can enhance the quality of error-prone individual sensing from dynamic environments. In this paper, we compare the potential of different types of complex networks for such sensing enhancement. Numerical simulations on complex networks are complemented by a mean-field approach for limited connectivity that captures essential trends in dependencies. Our results show that, whilst bestowing advantages on a small group of agents, degree heterogeneity tends to impede overall sensing enhancement. In contrast, clustering and spatial structure play a more nuanced role depending on overall connectivity. We find that ring graphs exhibit superior enhancement for large connectivity and that random graphs outperform for small connectivity. Further exploring the role of clustering and path lengths in small-world models, we find that sensing enhancement tends to be boosted in the small-world regime.     

Scale free effects in world currency exchange network

A large collection of daily time series for 60 world currencies' exchange rates is considered. The correlation matrices are calculated and the corresponding Minimal Spanning Tree (MST) graphs are constructed for each of those currencies used as reference for the remaining ones. It is shown that multiplicity of the MST graphs' nodes to a good approximation develops a power like, scale free distribution with the scaling exponent similar as for several other complex systems studied so far. Furthermore, quantitative arguments in favor of the hierarchical organization of the world currency exchange network are provided by relating the structure of the above MST graphs and their scaling exponents to those that are derived from an exactly solvable hierarchical network model. A special status of the USD during the period considered can be attributed to some departures of the MST features, when this currency (or some other tied to it) is used as reference, from characteristics typical to such a hierarchical clustering of nodes towards those that correspond to the random graphs. Even though in general the basic structure of the MST is robust with respect to changing the reference currency some trace of a systematic transition from somewhat dispersed – like the USD case – towards more compact MST topology can be observed when correlations increase.