STAR Workshop on Random Graphs 2017.
Abstracts
| Speaker: | Marián Boguñá (University of Barcelona). |
| Title: | Toward a cosmological theory of complex networks |
| Abstract: | Structural and dynamical similarities of different real networks suggest that some universal laws might accurately describe the dynamics of these networks, albeit the nature and common origin of such laws remain elusive. Here we show that causal network representing the large-scale structure of spacetime in our accelerating universe is a power-law graph with strong clustering, similar to many complex networks such as the Internet, social or biological networks. We prove that this strcutural similarity is a consequence of the asymptotic equivalence between the large-scale growth dynamics of complex networks and causal networks. This equivalence suggests that unexpectedly similar laws govern the dynamics of complex networks and spacetime in the universe, with implications to network science and cosmology. However, our simple frameworks is unable to explain the emergence of community structure, a property that, along with scale-free degree distributions and strong clustering, is commonly found in real complex networks. Here we show how latent network geometry coupled with preferential attachment of the nodes to this geometry fills this gap. We call this mechanism geometric preferential attachment (GPA) and validate it against the Internet. GPA gives rise to soft communities that provide a different perspective on the community structure in networks. The connections between GPA and cosmological models, including inflation, are also discussed. |
| Speaker: | Angus Davidson (University of Bristol). |
| Title: | The Robot Crawler Model |
| Abstract: | Web crawlers are used by internet search engines to gather information about the web graph. In this talk we investigate a simple process which models this software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, complete k-partite graphs and secondly, sparse Erdos-Renyi random graphs. Our work follows on from a paper of Bonato et. al. who introduced the model. |
| Speaker: | Sander Dommers (Ruhr-University Bochum). |
| Title: | Metastability of the Ising model on random regular graphs at zero temperature |
| Abstract: | We study the metastability of the ferromagnetic Ising model on a random $r$-regular graph in the zero temperature limit. We prove that in the presence of a small positive external field the time that it takes to go from the all minus state to the all plus state behaves like $\exp(\beta n (r/2+O(\sqrt{r})))$ when the inverse temperature $\beta\rightarrow\infty$ and the number of vertices $n$ is large enough but fixed. For the proof it is necessary to understand the global structure of the random graph, especially bounds on the isoperimetric number of random regular graphs are used. These bounds are combined with the so-called pathwise approach to metastability. |
| Speaker: | Henk Don (Radboud University). |
| Title: | Non-negative matrix factorization in the SIS model |
| Abstract: |
In this talk I will briefly introduce the SIS epidemic model. We consider the SIS model with general infectionrate matrix A. A central question for this model is when a metastable state exists. Using a nonnegative
matrix factorization to approximate A, we are able to identify when a metastable state
can be expected, and that the metastable distribution, under certain conditions, will be a normal distribution with known expectation and covariance. The factorization of A (which reduces the complexity of the model) can be seen as a clustering of the nodes into groups with approximately the same behaviour.
Joint work with Eric Cator and Piet van Mieghem |
| Speaker: | Sergey Frenkel (Russian Academy of Sciences). |
| Title: | Random graphs based model for malware detection |
| Abstract: |
A similarity estimation is a key operation in malicious software (malware) detection. In dynamic approaches to malware detection, that is analyzing the behavior of a malicious code while it is being executed in a controlled environment, sequences of system calls are compared from their similarity point of view. These sequences are the traces of software executed.
One of approaches to the similarity estimation is based on the notion of call graph abstraction of the traces, which is a representation of the call sequences as a directed graph in which functions are modeled as vertices, and calls between those functions as directed edges. Various graph similarity measures have been proposed for the traces similarity comparison. Many approaches are based on graph edit distance (GED). Graph edit distance is obtained by computing how many alterations have to be done to graph G for it to become isomorphic with graph H. In fact, the GED is size of the symmetric difference of the edge sets. The GED may be used for clustering of malicious samples in off-line training and then examine the on-line data for being benign or malicious by the distance of the data from existing clusters defined in the training phase. The main difficult of such approach is its computational complexity. Therefore, the GED-based clustering problems should be formulated as finding of minimal set of samples allowing an $\epsilon$-approximation of the similarity metric with time polynomial complexity. This presentation describes and analyzes the reasonability to use Markov graph model for the problem to find the number of the malicious traces samples required for edit distance appropriate approximation. The Markov graph is a random graph that is obtained by associating a random variable $X_i$ to node $i$, that takes values from an alphabet. For our case, this is $n$-grams extracted from the traces. The possibility to use undirected graph model to represent the traces can be justified due to Markov Edit Distance is defined that account for the local interactions among adjacent nodes. Some statistical aspects of the random graph model parameters estimation also will be presented. This work was partially supported by the Russian Foundation for Basic Research under grant RFBR 15-07-05316. |
| Speaker: | Pim van der Hoorn (Northeastern University). |
| Title: | Generating maximally disassortative graphs with a given degree distribution |
| Abstract: | The correlation between the degrees of a randomly sampled edge, called degree-degree correlations, has become part of the standard set of topological features of networks. Many research has been done on finding consistent measures and null-models for these correlations as well as analyzing their impact on other properties of, and processes on networks. However, there are still many open questions related to these correlations, such as the existence and structure of graphs with extreme (positive)negative correlations. We consider the optimization problem of generating graphs with a given degree sequence, that minimize degree-degree correlations, as measured by Spearman’s rho. We describe a deterministic algorithm, based on a minimizing partition approach, that solves this problem. We then extend this algorithm to a probabilistic setting and show that this enables us to generate simple graphs with a given degree distribution, for which degree-degree correlations are minimized. By using the view point of the minimizing partition, we are able to obtain a complete characterization of the joint-degree distribution of these maximally dissassortative graphs, in terms of the size-biased degree distribution. This allows us to compute the minimal value of Spearman’s rho for graphs with a given degree distribution. With these results we can show that when the degree distribution is scale-free, the value of the exponent of the distribution, by itself, gives no guarantees for the minimal value of Spearman’s rho. In particular, given any exponent, we can construct a scale-free degree distribution such that this minimal value will be arbitrary close to zero. More interestingly, we show that for maximally disassortative graphs with either a Poisson or Pareto degree distribution, the minimal value of Spearman’s rho depends on, respectively, the mean and exponent, and we can tune this value between −1 and 0, by either increasing or decreasing these. For example, for a Pareto degree distribution with exponent $\gamma = 2.5$, Spearman rho cannot be smaller than −0.5. This is a crucial observation, since it shows that, depending on the specific degree distribution, a graph with negative measured value for degree-degree correlations close to zero, can still have a maximally disassortative structure. |
| Speaker: | Mihyun Kang (Graz University of Technology). |
| Title: | Homological connectivity of random hypergraphs |
| Abstract: |
We consider 2-dimensional simplicial complexes that are generated from
the binomial random 3-uniform hypergraph by taking the
downward-closure. We determine when this simplicial complex is
homologically connected, meaning that its zero-th and first homology
groups with coefficients in $\mathbb{F}_2$ vanish. Although this is
not intrinsically a monotone property, we show that it nevertheless
has a single sharp threshold, and indeed prove a hitting time result
relating the connectedness to the disappearance of the last minimal
obstruction.
Joint work with: Oliver Cooley, Penny Haxell, and Philipp Sprüssel |
| Speaker: | Adam Lipowski (Adam Mickiewicz University). |
| Title: | Agreement dynamics on random graphs |
| Abstract: |
Sufficiently dense random graphs are expected to support long-range ordering. In particular, emergence of ferromagnetism in Ising model on random graph is known to appear exactly at the percolation transition. We show that this is not the case for directed random graphs, where ferromagnetism appears but for substantially denser random graphs. Also the dynamics of Ising models on undirected and directed random graphs much differ. While the undirected random quench gets trapped in the disordered configuration, the directed graph version evolves toward the configuration with spontaneously broken symmetry. We argue that directed version of Ising model generates some kind of interfacial noise and that might explain why it differs from the undirected version. We also discuss the behaviour of other agreement dynamics systems (Naming Game, Voter model) on random graphs.
References: 1) A. Lipowski et al., Agreement dynamics on directed random graphs, preprint: https://arxiv.org/abs/1605.00310 2) A. Lipowski et al. Phase transitions in Ising models on directed networks, Phys. Rev. E 92, 052811 (2015). Preprint version: https://arxiv.org/abs/1510.00423 |
| Speaker: | Rajko Nenadov (Monash University). |
| Title: | Optimal induced universal graphs for bounded-degree graphs |
| Abstract: | We show that for any constant $\Delta \ge 2$, there exists a graph $\Gamma$ with $O(n^{\Delta / 2})$ vertices which contains every $n$-vertex graph with maximum degree $\Delta$ as an induced subgraph. For odd $\Delta$ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least $\Omega(n^{\Delta/2})$ vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of $\Gamma$ is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph $H$ on $n$ vertices with maximum degree at most $\Delta$, an induced subgraph of $\Gamma$ isomorphic to $H$. |
| Speaker: | Angelica Pachon (Torino University). |
| Title: | On the continuous-time limit of the Barabási-Albert random graph |
| Abstract: |
We prove a weak convergence of the Barabási-Albert random graph to a modified Yule model, where the Yule process that represents the appearance of in-links must be conditioned to start with a fix number of individuals. Through this relation we explain why asymptotic properties of a random vertex in the Barabási-Albert model, coincide with the asymptotic properties of a random genus in the Yule model. As a by-product of our analysis, we obtain the explicit expression of the limit degree distribution for the Barabási-Albert model. This result is given in (2) using combinatoric techniques.
References to traditional and recent result of Preferential attachment models are also discussed. References: 1) A. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509-512, 1999. 2) B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The Degree Sequence of a Scale-free Random Graph Process. Random Struct. Algorithms, 18(3):279-290, 2001. 3) R. Durrett. Random Graph Dynamics. Cambridge University Press, New York, NY, USA, 2006. 4) A. Pachon, F. Polito and L. Sacerdote, Preferential attachment models. Discrete and Continuous time relation. J. Stat. Phys. 162 (6):1608-1638, 2016. |
| Speaker: | Merlijn Staps (Utrecht University). |
| Title: | The diameter of hyperbolic random graphs |
| Abstract: |
We study a model of random geometric graphs in the hyperbolic plane, that was introduced recently by Krioukov et al. These graphs are constructed by sampling a
fixed number of points randomly from a disk in the hyperbolic plane
and then connecting pairs of points by an edge if their hyperbolic
distance is less than a certain threshold value. This random graph
model recapitulates various properties of complex networks, including
a scale-free degree distribution, clustering and short distances.
In this talk we will consider the graph diameter of the largest component.
We give a logarithmic upper for this quantity (the upper bound holds
a.a.s., that is with probability tending to one as the number of nodes
tends to infinity). This improves over (a.a.s.) polylogarithmic upper
bounds in earlier works by Kiwi-Mitsche and Friedrich-Krohmer, and
matches an a.a.s. lower bound by Friedrich-Krohmer.
Based on joint work with Tobias Müller. |
| Speaker: | Nicos Starreveld (University of Amsterdam). |
| Title: | Dynamic Erdös-Rényi graphs |
| Abstract: |
We propose two classes of dynamic versions of the classical Erdös-Rényi graph:
one in which the transition rates are governed by an external regime process,
and one in which the transition rates are periodically resampled. For both models we consider the evolution of the number of edges present, with explicit results for the corresponding moments, functional central limit theorems and large deviations asymptotics.
Joint work with Michel Mandjes (UvA), René Bekker (VU Amsterdam), Peter Spreij (UvA) |
| Speaker: | Clara Stegehuis (Technische Universiteit Eindhoven). |
| Title: | Clustering in random graphs with natural cutoffs and single-edge constraints |
| Abstract: |
We investigate the presence of triangles in two random graph models with single-edge constraints: the erased configuration model, and a model where hidden variables determine the connection probabilities between different vertices. Specifically, we study networks with a power-law degree distribution with $2<\tau< 3 $, so that the degrees have infinite variance. We show that only triangles between vertices of degree $\Theta(\sqrt{N})$ contribute to the clustering coefficient. We also study the local clustering coefficient of nodes with degree $k$, $c(k)$. The single edge constraints of the erased configuration model and the hidden variable model cause $c(k)$ to be constant for small values of $k$ and to decay for $k>\sqrt{N}$. Again, the only contribution to $c(k)$ comes from triangles between vertices with degrees in very specific regimes, depending on $k$.
Joint work with: Remco van der Hofstad, Pim van der Hoorn, A.J.E.M. Janssen, Johan S.H. van Leeuwaarden and Nelly Litvak |
| Speaker: | Lorenzo Taggi (TU-Darmstadt). |
| Title: | Random permutations on graphs |
| Abstract: | We consider random permutations of the vertices of a graph such that every vertex is either mapped to a neighbour with a penalization factor $\alpha$ or it is mapped to itself with no penalization . If $\mu$ is the connective constant of an infinite vertex-transitive graph, we prove non-existence of long cycles for all $\alpha > \alpha_c$, where $\alpha_c < \log(mu)$. Moreover, we consider the $d$-dimensional cubic lattice and we condition on an open cycle connecting two opposite sides of a box of side length $n$. We prove convergence to a straight line when the graph is rescaled by $n$. More specifically, we prove that the length of the open cycle is at most $n + O( \sqrt{n} \log{n} )$ when $\alpha$ is large enough. When $\alpha$ is large, the open cycle is expected to converge to Brownian bridge under diffusive scaling. Furthermore, long cycles are expected to be observed for $\alpha$ small enough on certain classes of graphs, for example on $Z^d$, $d > 2$. |
| Speaker: | Vincent Tassion (University of Geneva/ETH Zürich). |
| Title: | Sharpness results via randomized algorithms |
| Abstract: |
In this talk, we will provide a new proof of exponential
decay/mean-field lower bound for Bernoulli percolation based on
randomized algorithms. This proof does not rely on the domain Markov
property or the BK inequality. In particular, it extends to continuum
percolation models such as Boolean and Voronoi percolation in
arbitrary dimension, thus providing the first proof of sharpness of
the phase transition for these models.
Based on a joint work with H. Duminil-Copin and A. Raoufi. |
| Speaker: | Daniel Valesin (University of Groningen). |
| Title: | Spatial Gibbs random graphs |
| Abstract: |
Many real-world networks of interest are embedded in physical space.
We present a new random graph model aiming to reflect the interplay
between the geometries of the graph and of the underlying space. The
model favors configurations with small average graph distance between
vertices, but adding an edge comes at a cost measured according to the
geometry of the ambient physical space. In most cases, we identify the
order of magnitude of the average graph distance as a function of the
parameters of the model. As the proofs reveal, hierarchical structures
naturally emerge from our simple modeling assumptions. Moreover, a
critical regime exhibits an infinite number of phase transitions.
Joint work with Jean-Christophe Mourrat (ENS Lyon). |
| Speaker: | Nick Wormald (Monash University). |
| Title: | The probability of nonexistence of a subgraph in a moderately sparse random graph |
| Abstract: | We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph $G_0$ in the common random graph models $G(n,m)$ and $G(n,p)$. Our results apply when the average degrees of the random graphs are below the threshold at which each edge is included in a copy of $G_0$. For all strictly balanced subgraphs $G_0$, our results give much information on the distribution of the number of copies of $G_0$ that are not in large ''clusters'' of copies. The probability that a random graph in $G(n,p)$ has no copies of $G_0$ is shown to be given asymptotically by the exponential of a power series in $n$ and $p$, over a fairly wide range of $p$. A corresponding result is also given for $G(n,m)$, which gives an asymptotic formula for the number of graphs with $n$ vertices, $m$ edges and no copies of $G_0$, for the applicable range of $m$. |