We show that for a certain class of convex functions f, including the exponential functions x↦eλx with λ>0 a real number, and all the powers x↦xβ, x≥0 and β≥2 a real number, with a unique small exception, if (d1,...,dn) ranges over the degree sequences of graphs with n vertices and m edges and m≤n−1, then the maximum of ∑if(di) is uniquely attained by the degree sequence of a quasi-star graph, namely, a graph consisting of a star plus possibly additional isolated vertices. This result significantly extends a similar result in Ismailescu and Stefanica (2002). Dually, we show that for a certain class of concave functions g, including the negative exponential functions x↦1−e−λx with λ>ln(2) a real number, all the powers x↦xα, x≥0 and 0<α≤[Formula presented] for x≥0, if (d1,...,dn) ranges over the degree sequences of graphs with n vertices and m edges, then the minimum of ∑ig(di) is uniquely attained by the degree sequence of a quasi-complete graph, i.e., a graph consisting of a complete graph plus possibly an additional vertex connected to some but not all vertices of the complete graph, plus possibly isolated vertices. This result extends a similar result in the same paper.

Let X be a centered random vector in a finite-dimensional real inner product space E. For a subset C of the ambient vector space V of E and x,y is an element of V, write x <= Cy if y-x is an element of C. If C is a closed convex cone in E, then <= C is a preorder on V, whereas if C is a proper cone in E, then <= C is actually a partial order on V. In this paper, we give sharp Cantelli-type inequalities for generalized tail probabilities such as PrX >= Cb for b is an element of V. These inequalities are obtained by "scalarizing" X >= Cb via cone duality and then by minimizing the classical univariate Cantelli's bound over the scalarized inequalities. Three diverse applications to random matrices, tails of linear images of random vectors, and network homophily are also given.

In this paper, we provide explicit upper bounds on some distances between the (law of the) output of a random Gaussian neural network and (the law of) a random Gaussian vector. Our main results concern deep random Gaussian neural networks with a rather general activation function. The upper bounds show how the widths of the layers, the activation function, and other architecture parameters affect the Gaussian approximation of the output. Our techniques, relying on Stein's method and integration by parts formulas for the Gaussian law, yield estimates on distances that are indeed integral probability metrics and include the convex distance. This latter metric is defined by testing against indicator functions of measurable convex sets and so allows for accurate estimates of the probability that the output is localized in some region of the space, which is an aspect of a significant interest both from a practitioner's and a theorist's perspective. We illustrated our results by some numerical examples.

For a graph G and a positive integer c, let Mc(G) be the size of a subgraph of G induced by a randomly sampled subset of c vertices. Second-order moments of Mc(G) encode part of the structure of G. We use this fact, coupled to classical moment inequalities, to prove graph theoretical results, to give combinatorial identities, to bound the size of the c-densest subgraph from below and the size of the c-sparsest subgraph from above, and to provide bounds for approximate enumeration of trivial subgraphs.

In this talk we provide explicit upper bounds on some distances between the (law of the) output of a random Gaussian neural network and (the law of) a random Gaussian vector. Our main results concern deep random Gaussian neural networks, with a rather general activation function. The upper bounds show how the widths of the layers, the activation function and other architecture parameters affect the Gaussian approximation of the output. Our techniques, relying on Stein's method and integration by parts formulas for the Gaussian law, yield estimates on distances which are indeed integral probability metrics, and include the convex distance. This latter metric is defined by testing against indicator functions of measurable convex sets, and so allows for accurate estimates of the probability that the output is localized in some region of the space. Such estimates have a significant interest both from a practitioner's and a theorist's perspective.

Homophily is the principle whereby "similarity breeds connections."We give a quantitative formulation of this principle within networks. Given a network and a labeled partition of its vertices, the vector indexed by each class of the partition, whose entries are the number of edges of the subgraphs induced by the corresponding classes, is viewed as the observed outcome of the random vector described by picking labeled partitions at random among labeled partitions whose classes have the same cardinalities as the given one. This is the recently introduced random coloring model for network homophily. In this perspective, the value of any homophily score ?, namely, a nondecreasing real-valued function in the sizes of subgraphs induced by the classes of the partition, evaluated at the observed outcome, can be thought of as the observed value of a random variable. Consequently, according to the score ?, the input network is homophillic at the significance level ? whenever the one-sided tail probability of observing a value of ? at least as extreme as the observed one is smaller than ?. Since, as we show, even approximating ? is an NP-hard problem, we resort to classical tails inequality to bound ? from above. These upper bounds, obtained by specializing ?, yield a class of quantifiers of network homophily. Computing the upper bounds requires the knowledge of the covariance matrix of the random vector, which was not previously known within the random coloring model. In this paper we close this gap. Interestingly, the matrix depends on the input partition only through the cardinalities of its classes and depends on the network only through its degrees. Furthermore all the covariances have the same sign, and this sign is a graph invariant. Plugging this structure into the bounds yields a meaningful, easy to compute class of indices for measuring network homophily. As demonstrated in real-world network applications, these indices are effective and reliable, and may lead to discoveries that cannot be captured by the current state of the art.

Path graphs are intersection graphs of paths in a tree. We start from the characterization of path graphs by Monma and Wei (1986) [14] and we reduce it to some 2-coloring subproblems, obtaining the first characterization that directly leads to a polynomial recognition algorithm. Then we introduce the collection of the attachedness graphs of a graph and we exhibit a list of minimal forbidden 2-edge colored subgraphs in each of the attachedness graph.

It has been observed in different kinds of networks, such as social or biological ones, a typical behavior inspired by the general principle 'similarity breeds connections'. These networks are defined as homophilic as nodes belonging to the same class preferentially interact with each other. In this work, we present HONTO (HOmophily Network TOol), a user-friendly open-source Python3 package designed to evaluate and analyze homophily in complex networks. The tool takes in input from the network along with a partition of its nodes into classes and yields a matrix whose entries are the homophily/heterophily z-score values. To complement the analysis, the tool also provides z-score values of nodes that do not interact with any other node of the same class. Homophily/heterophily z-scores values are presented as a heatmap allowing a visual at-a-glance interpretation of results.

We present a new method for assessing and measuring homophily in networks whose nodes have categorical attributes, namely when the nodes of networks come partitioned into classes (colors). We probe this method in two different classes of networks: (i) protein-protein interaction (PPI) networks, where nodes correspond to proteins, partitioned according to their functional role, and edges represent functional interactions between proteins (ii) Pokec on-line social network, where nodes correspond to users, partitioned according to their age, and edges respresent friendship between users.Similarly to other classical and well consolidated approaches, our method compares the relative edge density of the subgraphs induced by each class with the corresponding expected relative edge density under a null model. The novelty of our approach consists in prescribing an endogenous null model, namely, the sample space of the null model is built on the input network itself. This allows us to give exact explicit expression for the z-score of the relative edge density of each class as well as other related statistics. The z-scores directly quantify the statistical significance of the observed homophily via ?eby?ëv inequality. The expression of each z-score is entered by the network structure through basic combinatorial invariant such as the number of subgraphs with two spanning edges. Each z-score is computed in O(n+ m) time for a network with n nodes and m edges. This leads to an overall efficient computational method for assesing homophily. We complement the analysis of homophily/heterophily by considering z-scores of the number of isolated nodes in the subgraphs induced by each class, that are computed in O(nm) time. Theoretical results are then exploited to show that, as expected, both the analyzed network classes are significantly homophilic with respect to the considered node properties.

Bandelt and Mulder’s structural characterization of bipartite distance hereditary graphs asserts that such graphs can be built inductively starting from a single vertex and by repeatedly adding either pendant vertices or twins (i.e., vertices with the same neighborhood as an existing one). Dirac and Duffin’s structural characterization of 2–connected series–parallel graphs asserts that such graphs can be built inductively starting from a single edge by adding either edges in series or in parallel. In this paper we give an elementary proof that the two constructions are the same construction when bipartite graphs are viewed as the fundamental graphs of a graphic matroid. We then apply the result to re-prove known results concerning bipartite distance hereditary graphs and series–parallel graphs and to provide a new class of polynomially-solvable instances for the integer multi-commodity flow of maximum value.

We present a new method for assessing homophily in networks whose vertices have categorical attributes, namely when the vertices of networks come partitioned into classes. We apply this method to Protein- Protein Interaction networks, where vertices correspond to proteins, partitioned according to they func- tional role, and edges represent potential interactions between proteins. Similarly to other classical and well consolidated approaches, our method compares the relative edge density of the subgraphs induced by each class with the corresponding expected relative edge density under a null model. The novelty of our approach consists in prescribing an endogenous null model, namely, the sample space of the null model is built on the input network itself. This allows us to give exact explicit expression for the z-score of the relative edge density of each class as well as other related statistics. The z-scores directly quantify the statistical significance of the observed homophily via ?Ceby?s ?ev inequality. The expression of each z-score is entered by the network structure through basic combinatorial invariant such as the number of subgraphs with two spanning edges. Each z-score is computed in O(n3) worst-case time for a network with n vertices. This leads to an overall effective computational method for assesing homophily. Theoretical results are then exploited to prove that Protein-Protein Interaction networks networks are significantly homophillous.

Bandelt and Mulder's structural characterization of bipartite distance hereditary graphs 16 asserts that such graphs can be built inductively starting from a single vertex and by re- 17 peatedly adding either pendant vertices or twins (i.e., vertices with the same neighborhood 18 as an existing one). Dirac and Duffin's structural characterization of 2-connected series- 19 parallel graphs asserts that such graphs can be built inductively starting from a single edge 20 by adding either edges in series or in parallel. In this paper we give an elementary proof 21 that the two constructions are the same construction when bipartite graphs are viewed as 22 the fundamental graphs of a graphic matroid. We then apply the result to re-prove known 23 results concerning bipartite distance hereditary graphs and series-parallel graphs and to 24 provide a new class of polynomially-solvable instances for the integer multi-commodity 25 flow of maximum value.

Nel documento si fornisce una caratterizzazione costruttiva dei Path Graph alternativa a quella già nota e data mediante famiglie di sottografi proibiti.

The class of Bipartite Distance Hereditary (BDH) graphs is the intersection between bipartite domino-free and chordal bipartite graphs. Graphs in both the latter classes have linearly many maximal bicliques, implying the existence of polynomial-time algorithms for computing the associated Galois lattice. Such a lattice can indeed be built in O(m?n)O(m?n)worst-case time for a domino-free graph with mm edges and nn vertices. In Apollonio et al. (2015), BDH graphs have been characterized as those bipartite graphs whose Galois lattice is tree-like. In this paper we give a sharp upper bound on the number of maximal bicliques of a BDH graph and we provide an O(m)O(m) time-worst-case algorithm for incrementally computing its Galois lattice. The algorithm in turn implies a constructive proof of the if part of the characterization above. Moreover, we give an O(n)O(n) worst-case space and time encoding of both the input graph and its Galois lattice, provided that the reverse of a Bandelt and Mulder building sequence is given.

We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois lattice of a bipartite graph is tree-like if and only if the graph is a bipartite distance hereditary graph. Relations with the class of Ptolemaic graphs are discussed and exploited to give an alternative proof of the result. (C) 2015 Elsevier B.V. All rights reserved.

A {0, 1}-matrix A is balanced if it does not contain a submatrix of odd order having exactly two 1's per row and per column. A graph is balanced if its clique-matrix is balanced. No characterization of minimally unbalanced graphs is known, and even no conjecture on the structure of such graphs has been posed, contrary to what happened for perfect graphs. In this paper, we provide such a characterization for the class of diamond-free graphs and establish a connection between minimally unbalanced diamond-free graphs and Dyck-paths.

Given a simple undirected graph G and a positive integer s, the maximum vertex coverage problem (MVC) is the problem of finding a set U of s vertices of G such that the number of edges having at least one endpoint in U is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37-48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv: 1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a 4/5-approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC.