BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Anthony Bonato appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Counts of small subgraphs, or graphlet counts, are widely applicable to measure graph similarity. Computing graphlet counts can be computationally expensive and may pose obstacles in network analysis. We study the role of cliques in graphlet counts as a method for graph similarity in social networks. Higher-order clustering coefficients and the Pivoter algorithm for exact clique counts are employed
We introduce a new graph parameter called the cooling number, inspired by the spread of influence in networks and its predecessor, the burning number. The cooling number measures the speed of a slow-moving contagion in a graph; the lower the cooling number, the faster the contagion spreads. We provide tight bounds on the cooling number via a graph's order and diameter. Using isoperimetric results, we derive the cooling number of Cartesian grids. The cooling number is studied in graphs generated by the Iterated Local Transitivity model for social networks. We conclude with open problems.
The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best-known result was for graphs with minimum degree $23$.
We consider a new model for complex networks whose underlying mechanism is extending dense subgraphs. In the frustum model, we iteratively extend cliques over discrete-time steps. For many choices of the underlying parameters, graphs generated by the model densify over time. In the special case of the cone model, generated graphs provably satisfy properties observed in real-world complex networks such as the small world property and bad spectral expansion. We finish with a set of open problems and next steps for the frustum model.
We provide new constructions of Meyniel extremal graphs, which are families of graphs with the conjectured largest asymptotic cop number. Using spanning subgraphs, we prove that there are an exponential number of new Meyniel extremal families with specified degrees. Using a linear programming problem on hypergraphs, we explore the degrees in families that are not Meyniel extremal. We give the best-known upper bound on the cop number of vertex-transitive graphs with a prescribed degree. We find new Meyniel extremal families of regular graphs with large chromatic number, large diameter, and explore the connection between Meyniel extremal graphs and bipartite graphs.
In the Localization game played on graphs, a set of cops uses distance probes to identify the location of an invisible robber. We present an extension of the game and its main parameter, the localization number, to directed graphs. We present several bounds on the localization number of a directed graphs, including a tight bound via strong components, a bound using a linear programming problem on hypergraphs, and bounds in terms of pathwidth and DAG-width. A family of digraphs of order $n$ is given with localization number $(1-o(1))n/2$. We investigate the localization number of random and quasi-random tournaments, and apply our results to doubly regular tournaments, which include Paley tournaments.
In adversarial networks, edges correspond to negative interactions such as competition or dominance. We introduce a new type of node called a low-key leader in adversarial networks, distinguished by contrasting the centrality measures of CON score and PageRank. We present a novel hypothesis that low-key leaders are ubiquitous in adversarial networks and provide evidence by considering data from real-world networks, including dominance networks in 172 animal populations, trading networks between G20 nations, and Bitcoin trust networks. We introduce a random graph model that generates directed graphs with low-key leaders.
The distinguishing number of a structure is the smallest size of a partition of its elements so that only the trivial automorphism of the structure preserves each cell of the partition. We show that for any countable subset of the positive real numbers, the corresponding countable homogeneous Urysohn metric space, when it exists, has distinguishing number 2 or the distinguishing number is infinite. While it is known that a sufficiently large finite primitive structure has distinguishing number 2, unless its automorphism group is the full symmetric group or alternating group, the infinite case is open and these countable Urysohn metric spaces provide further confirmation toward the conjecture that all primitive homogeneous countably infinite structures have distinguishing number 2 or else the distinguishing number is infinite.
We consider Flipping Coins, a partizan version of the impartial game Turning Turtles, played on lines of coins. We show the values of this game are numbers, and these are found by first applying a reduction, then decomposing the position into an iterated ordinal sum. This is unusual since moves in the middle of the line do not eliminate the rest of the line. Moreover, when $G$ is decomposed into lines $H$ and $K$, then $G=(H:K^R)$. This is in contrast to Hackenbush Strings where $G= (H:K)$.
Complex networks are pervasive in the real world, capturing dyadic interactions between pairs of vertices, and a large corpus has emerged on their mining and modeling. However, many phenomena are comprised of polyadic interactions between more than two vertices. Such complex hypergraphs range from emails among groups of individuals, scholarly collaboration, or joint interactions of proteins in living cells. A key generative principle within social and other complex networks is transitivity, where friends of friends are more likely friends. The previously proposed Iterated Local Transitivity (ILT) model incorporated transitivity as an evolutionary mechanism. The ILT model provably satisfies many observed properties of social networks, such as densification, low average distances, and high clustering coefficients. We propose a new, generative model for complex hypergraphs based on transitivity, called the Iterated Local Transitivity Hypergraph (or ILTH) model. In ILTH, we iteratively apply the principle of transitivity to form new hypergraphs. The resulting model generates hypergraphs simulating properties observed in real-world complex hypergraphs, such as densification and low average distances. We consider properties unique to hypergraphs not captured by their 2-section. We show that certain motifs, which are specified subhypergraphs of small order, have faster growth rates in ILTH hypergraphs than in random hypergraphs with the same order and expected average degree. We show that the graphs admitting a homomorphism into the 2-section of the initial hypergraph appear as induced subgraphs in the 2-section of ILTH hypergraphs. We consider new and existing hypergraph clustering coefficients, and show that these coefficients have larger values in ILTH hypergraphs than in comparable random hypergraphs.
Graph burning is a deterministic, discrete-time process that models how influence or contagion spreads in a graph. Associated to each graph is its burning number, which is a parameter that quantifies how quickly the influence spreads. We survey results on graph burning, focusing on bounds, conjectures, and algorithms related to the burning number. We will discuss state-of-the-art results on the burning number conjecture, burning numbers of graph classes, and algorithmic complexity. We include a list of conjectures, variants, and open problems on graph burning.
We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The corresponding optimization parameter for a graph $G$ is called the localization number and is written $ζ(G)$. We settle a conjecture of \cite{nisse1} by providing an upper bound on the localization number as a function of the chromatic number. In particular, we show that every graph with $ζ(G) \le k$ has degeneracy less than $3^k$ and, consequently, satisfies $χ(G) \le 3^{ζ(G)}$. We show further that this degeneracy bound is tight. We also prove that the localization number is at most 2 in outerplanar graphs, and we determine, up to an additive constant, the localization number of hypercubes.
Graph burning is a discrete-time process on graphs, where vertices are sequentially burned, and burned vertices cause their neighbours to burn over time. We consider extremal properties of this process in the new setting where the underlying graph is also changing at each time-step. The main focus is on the possible densities of burning vertices when the sequence of underlying graphs are growing grids in the Cartesian plane, centred at the origin. If the grids are of height and width $2cn+1$ at time $n$, then all values in $\left [ \frac{1}{2c^2} , 1 \right ]$ are possible densities for the burned set. For faster growing grids, we show that there is a threshold behaviour: if the size of the grids at time $n$ is $ω(n^{3/2})$, then the density of burned vertices is always $0$, while if the grid sizes are $Θ(n^{3/2})$, then positive densities are possible. Some extensions to lattices of arbitrary but fixed dimension are also considered.
We introduce the Iterated Global model as a deterministic graph process that simulates several properties of complex networks. In this model, for every set $S$ of nodes of a prescribed cardinality, we add a new node that is adjacent to every node in $S$. We focus on the case where the size of $S$ is approximately half the number of nodes at each time-step, and we refer to this as the half-model. The half-model provably generate graphs that densify over time, have bad spectral expansion, and low diameter. We derive the clique, chromatic, and domination numbers of graphs generated by the model.
We study $p$-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or $1$-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success $p$ is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal in 1980. Then in 2003, Alpern and Gal [The Theory of Search Games and Rendezvous] proposed a so-called monotone solution for searching the line ($2$-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the $2$-rays problem must be monotone. We disprove this conjecture when the search domain is the half-line ($1$-ray). We provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call $t$-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with $t$, and for all $p \in (0,1)$. The value of $t$ quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.
We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive integer $t$ is fixed, and the cops are required to capture the robber in at most $t$ time-steps in each play. The associated optimization parameter is the eternal cop number, denoted by $c_t^{\infty},$ which equals the eternal domination number in the case $t=1,$ and the cop number for sufficiently large $t.$ We study the complexity of Cops and Eternal Robbers, and show that game is NP-hard when $t$ is a fixed constant and EXPTIME-complete for large values of $t$. We determine precise values of $c_t^{\infty}$ for paths and cycles. The eternal cop number is studied for retracts, and this approach is applied to give bounds for trees, as well as for strong and Cartesian grids.
We introduce a new directed graph model for social networks, based on the transitivity of triads. In the Iterated Local Directed Transitivity (ILDT) model, new nodes are born over discrete time-steps, and inherit the link structure of their parent nodes. The ILDT model may be viewed as a directed analogue of the ILT model for undirected graphs introduced in \cite{ilt}. We investigate network science and graph theoretical properties of ILDT digraphs. We prove that the ILDT model exhibits a densification power law, so that the digraphs generated by the models densify over time. The number of directed triads are investigated, and counts are given of the number of directed 3-cycles and transitive $3$-cycles. A higher number of transitive 3-cycles are generated by the ILDT model, as found in real-world, on-line social networks. In many instances of the chosen initial digraph, the model eventually generates graphs with Hamiltonian directed cycles. We finish with a discussion of the eigenvalues of the adjacency matrices of ILDT directed graphs, and provide further directions.
We consider the localization number and metric dimension of certain graphs of diameter $2$, focusing on families of Kneser graphs and graphs without 4-cycles. For the Kneser graphs with diameter $2$, we find upper and lower bounds for the localization number and metric dimension, and in many cases these parameters differ only by an additive constant. Our results on the metric dimension of Kneser graphs improve on earlier ones, yielding exact values in infinitely many cases. We determine bounds on the localization number and metric dimension of Moore graphs of diameter $2$ and polarity graphs.
We study the localization number of incidence graphs of designs. In the localization game played on a graph, the cops attempt to determine the location of an invisible robber via distance probes. The localization number of a graph $G$, written $ζ(G)$, is the minimum number of cops needed to ensure the robber's capture. We present bounds on the localization number of incidence graphs of balanced incomplete block designs. Exact values of the localization number are given for the incidence graphs of projective and affine planes. Bounds are given for Steiner systems and for transversal designs.
Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, Bonato, Janssen, and Roshanbin [Burning a Graph as a Model of Social Contagion, Lecture Notes in Computer Science 8882 (2014) 13-22] define the burning number $b(G)$ of a graph $G$ as the smallest integer $k$ for which there are vertices $x_1,\ldots,x_k$ such that for every vertex $u$ of $G$, there is some $i\in \{ 1,\ldots,k\}$ with ${\rm dist}_G(u,x_i)\leq k-i$, and ${\rm dist}_G(x_i,x_j)\geq j-i$ for every $i,j\in \{ 1,\ldots,k\}$. For a connected graph $G$ of order $n$, they prove that $b(G)\leq 2\left\lceil\sqrt{n}\right\rceil-1$, and conjecture $b(G)\leq \left\lceil\sqrt{n}\right\rceil$. We show that $b(G)\leq \sqrt{\frac{32}{19}\cdot \frac{n}{1-ε}}+\sqrt{\frac{27}{19ε}}$ and $b(G)\leq \sqrt{\frac{12n}{7}}+3\approx 1.309 \sqrt{n}+3$ for every connected graph $G$ of order $n$ and every $0<ε<1$. For a tree $T$ of order $n$ with $n_2$ vertices of degree $2$, and $n_{\geq 3}$ vertices of degree at least $3$, we show $b(T)\leq \left\lceil\sqrt{(n+n_2)+\frac{1}{4}}+\frac{1}{2}\right\rceil$ and $b(T)\leq \left\lceil\sqrt{n}\right\rceil+n_{\geq 3}$. Furthermore, we characterize the binary trees of depth $r$ that have burning number $r+1$.
We investigate social networks of characters found in cultural works such as novels and films. These character networks exhibit many of the properties of complex networks such as skewed degree distribution and community structure, but may be of relatively small order with a high multiplicity of edges. Building on recent work of beveridge, we consider graph extraction, visualization, and network statistics for three novels: Twilight by Stephanie Meyer, Steven King's The Stand, and J.K. Rowling's Harry Potter and the Goblet of Fire. Coupling with 800 character networks from films found in the http://moviegalaxies.com/ database, we compare the data sets to simulations from various stochastic complex networks models including random graphs with given expected degrees (also known as the Chung-Lu model), the configuration model, and the preferential attachment model. Using machine learning techniques based on motif (or small subgraph) counts, we determine that the Chung-Lu model best fits character networks and we conjecture why this may be the case.
We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered.
We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is strictly greater than 1/2. We present asymptotic results for the zombie numbers of several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and Cartesian and toroidal grids.
Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is \textbf{NP}-complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed.
We introduce a new graph parameter called the burning number, inspired by contact processes on graphs such as graph bootstrap percolation, and graph searching paradigms such as Firefighter. The burning number measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We provide a number of properties of the burning number, including characterizations and bounds. The burning number is computed for several graph classes, and is derived for the graphs generated by the Iterated Local Transitivity model for social networks.
We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from an $m$-dimensional metric space with power-law distributed influence regions best fits samples from real-world networks when $m$ scales logarithmically with the number of nodes of the network. This supports a logarithmic dimension hypothesis, and we provide evidence with two different social networks, Facebook and LinkedIn. Further, we employ two different methods for confirming the hypothesis: the first uses the distribution of motif counts, and the second exploits the eigenvalue distribution.
We consider isomorphism properties of infinite random geometric graphs defined over a variety of metrics. In previous work, it was shown that for $\mathbb{R}^n$ with the $L_{\infty}$-metric, the infinite random geometric graph is, with probability 1, unique up to isomorphism. However, in the case $n=2$ this is false with either of the $L_2$-metric. We generalize this result to a large family of metrics induced by norms. Within this class of metric spaces, we show that the infinite geometric graph is not unique up to isomorphism if it has the new property which we name truncating: each step-isometry from a dense set to itself is an isometry. As a corollary, we derive that the infinite random geometric graph defined in $L_p$ space is not unique up to isomorphism with probability 1 for all finite $p>1.$
We consider the domination number for on-line social networks, both in a stochastic network model, and for real-world, networked data. Asymptotic sublinear bounds are rigorously derived for the domination number of graphs generated by the memoryless geometric protean random graph model. We establish sublinear bounds for the domination number of graphs in the Facebook 100 data set, and these bounds are well-correlated with those predicted by the stochastic model. In addition, we derive the asymptotic value of the domination number in classical random geometric graphs.
In this short note, we supply a new upper bound on the cop number in terms of tree decompositions. Our results in some cases extend a previously derived bound on the cop number using treewidth.
We supply an upper bound on the distinguishing chromatic number of certain infinite graphs satisfying an adjacency property. Distinguishing proper $n$-colourings are generalized to the new notion of distinguishing homomorphisms. We prove that if a graph $G$ satisfies the connected existentially closed property and admits a homomorphism to $H$, then it admits continuum-many distinguishing homomorphisms from $G$ to $H$ join $K_2.$ Applications are given to a family universal $H$-colourable graphs, for $H$ a finite core.
We consider the number of independent sets in hypergraphs, which allows us to define the independence density of countable hypergraphs. Hypergraph independence densities include a broad family of densities over graphs and relational structures, such as $F$-free densities of graphs for a given graph $F.$ In the case of $k$-uniform hypergraphs, we prove that the independence density is always rational. In the case of finite but unbounded hyperedges, we show that the independence density can be any real number in $[0,1].$ Finally, we extend the notion of independence density via independence polynomials.
Meyniel's conjecture is one of the deepest open problems on the cop number of a graph. It states that for a connected graph $G$ of order $n,$ $c(G) = O(\sqrt{n}).$ While largely ignored for over 20 years, the conjecture is receiving increasing attention. We survey the origins of and recent developments towards the solution of the conjecture. We present some new results on Meyniel extremal families containing graphs of order $n$ satisfying $c(G) \ge d\sqrt{n},$ where $d$ is a constant.
We present a deterministic model for on-line social networks (OSNs) based on transitivity and local knowledge in social interactions. In the Iterated Local Transitivity (ILT) model, at each time-step and for every existing node $x$, a new node appears which joins to the closed neighbour set of $x.$ The ILT model provably satisfies a number of both local and global properties that were observed in OSNs and other real-world complex networks, such as a densification power law, decreasing average distance, and higher clustering than in random graphs with the same average degree. Experimental studies of social networks demonstrate poor expansion properties as a consequence of the existence of communities with low number of inter-community edges. Bounds on the spectral gap for both the adjacency and normalized Laplacian matrices are proved for graphs arising from the ILT model, indicating such bad expansion properties. The cop and domination number are shown to remain the same as the graph from the initial time-step $G_0$, and the automorphism group of $G_0$ is a subgroup of the automorphism group of graphs generated at all later time-steps. A randomized version of the ILT model is presented, which exhibits a tuneable densification power law exponent, and maintains several properties of the deterministic model.
We consider the minimum order graphs with a given cop number. We prove that the minimum order of a connected graph with cop number 3 is 10, and show that the Petersen graph is the unique isomorphism type of graph with this property. We provide the results of a computational search on the cop number of all graphs up to and including order 10. A relationship is presented between the minimum order of graph with cop number $k$ and Meyniel's conjecture on the asymptotic maximum value of the cop number of a connected graph.
In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the capture time of the $n$-dimensional hypercube is $Θ(n\ln n).$ Our methods include a novel randomized strategy for the players, which involves the analysis of the coupon-collector problem.
We consider the new game of Cops and Attacking Robbers, which is identical to the usual Cops and Robbers game except that if the robber moves to a vertex containing a single cop, then that cop is removed from the game. We study the minimum number of cops needed to capture a robber on a graph $G$, written $cc(G)$. We give bounds on $cc(G)$ in terms of the cop number of $G$ in the classes of bipartite graphs and diameter two, $K_{1,m}$-free graphs.
We examine a dynamic model for the disruption of information flow in hierarchical social networks by considering the vertex-pursuit game Seepage played in directed acyclic graphs (DAGs). In Seepage, agents attempt to block the movement of an intruder who moves downward from the source node to a sink. The minimum number of such agents required to block the intruder is called the green number. We propose a generalized stochastic model for DAGs with given expected total degree sequence. Seepage and the green number is analyzed in stochastic DAGs in both the cases of a regular and power law degree sequence. For each such sequence, we give asymptotic bounds (and in certain instances, precise values) for the green number.
We study the link structure of on-line social networks (OSNs), and introduce a new model for such networks which may help infer their hidden underlying reality. In the geo-protean (GEO-P) model for OSNs nodes are identified with points in Euclidean space, and edges are stochastically generated by a mixture of the relative distance of nodes and a ranking function. With high probability, the GEO-P model generates graphs satisfying many observed properties of OSNs, such as power law degree distributions, the small world property, densification power law, and bad spectral expansion. We introduce the dimension of an OSN based on our model, and examine this new parameter using actual OSN data. We discuss how the geo-protean model may eventually be used as a tool to group users with similar attributes using only the link structure of the network.
We introduce a new class of countably infinite random geometric graphs, whose vertices are points in a metric space, and vertices are adjacent independently with probability p if the metric distance between the vertices is below a given threshold. If the vertex set is a countable dense set in R^n equipped with the metric derived from the L_{\infty}-norm, then it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR_n, is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR_n. In contrast, we show that infinite random geometric graphs in R^2 with the Euclidean metric are not necessarily isomorphic.