 |
|
||||
- SHANKAR BHAMIDI, University of North Carolina, Chapel Hill
Aggregation models with limited choice and the multiplicative coalescent [PDF]
-
The last few years has seen an enormous amount of interest on various random graph models. A tremendous number of models have been proposed ranging from static models (such as the famous Erdos-Renyi random graph model and the configuration model) to more dynamic models, models that change over time such as the preferential attachment model. Many of these models are formed via the addition of edges to an existing configuration. In such models there exists a critical ``time'' $\lambda$ such that below this time, all components are small (the maximal component scales like $\log{n}$, where $n$ is the number of vertices) while above this time a giant component emerges (where a unique component which scales like $c n$). We study the emergence of the giant component in a particularly famous example called the Bohman-Frieze process that incorporates limited choice in this process of growth, wherein at each stage one chooses two edges uniformly at random and then uses the first if it connects two singletons, else we use the second edge. We study fine scaled asymptotics of the component sizes at criticality and show how after proper rescaling and recentering, the process of emergence of the giant component through the critical scaling window is described by the standard multiplicative coalescent.
Joint work with Xuan Wang and Amarjit Budhiraja at UNC Chapel Hill
- ANTHONY BONATO, Ryerson University
Seepage as a model of counter-terrorism [PDF]
-
\emph{Seepage} is a vertex-pursuit game played on directed acyclic graphs (or dags). Nowakowski et al.\ introduced Seepage is a mixture of firefighting and graph searching, inspired by efforts to stem the lava fkow from the Eldfell volcano in Iceland. One player (\emph{sludge}) moves from a source towards a sink in the dag, while the other player (\emph{greens}) attempts to prevent the sludge from reaching a sink by protecting nodes. The \emph{green number} of a dag is the minimum number of greens needed to stop the sludge from reaching a sink. We consider applications of Seepage to networks interdiction and the modelling of terrorist networks. Nodes of the network are viewed as members of a terrorist cell, and agents neutralize selected nodes in an attempt to disrupt messages moving from the cell’s leader to one of its foot soldiers. A stochastic model is introduced which generates dags with a prescribed degree sequence. We play a variant of Seepage on the model, and contrast results on the green number in the case of a constant versus a power law degree sequence.
- MARIA DEIJFEN, Stockholm University
Scale-free percolation [PDF]
-
The talk is concerned with a model for inhomogeneous long-range percolation on $\mathbb{Z}^d$ with potential applications in network modeling. Each vertex is independently assigned a non-negative random weight and the probability that there is an edge between two given vertices is then determined by a certain function of their weights and of the distance between them. The results concern the degree distribution in the resulting graph, the percolation properties of the graph and the graph distance between remote pairs of vertices. The model interpolates between long-range percolation and inhomogeneous random graphs, and is shown to inherit interesting features of both these model classes.
- MATT HURSHMAN, Dalhousie University
Model Selection for Social Networks using Graphlets [PDF]
-
Several network models have been proposed to explain the link structure observed in online social networks. Such models are usually justified by showing that they can replicate certain observed features of real networks, such as a power law degree distribution, a high degree of clustering, and the small world property. This talk will addresses the problem of choosing the model that best fits a given real world network. We implement a model selection method based on un-supervised learning. An alternating decision tree is trained using synthetic graphs generated according to each of the models under consideration. Graphs are represented as feature vectors incorporating the frequency counts of all connected subgraphs on 3 and 4 vertices as well as features describing the degree distribution and small world property. We show that the subgraph counts alone are sufficient in separating the training data. For the test data, we take four Facebook graphs from various American Universities. Our results show that models incorporating some form of the preferential attachment mechanism tend to perform the best.
- ALEX LOPEZ-ORTIZ, University of Waterloo
Broadcasting in Conflict-Aware Multi-Channel Networks [PDF]
-
We consider the broadcasting problem in conflict-aware multi-channel networks. These networks can be modeled as undirected graphs in which each edge is labeled with a channel, with the restriction that edges with the same channel cannot successfully transmit data to a node simultaneously. Using simple properties of graphs we give hardness results as well as efficient algorithms for various network topologies. We then give lower bounds for the number of rounds in balanced complete graphs, an important subset of multi-channel networks on complete graphs. Lastly we propose a channel assignment together with a broadcasting algorithm that completes the broadcast in two rounds.
- TOBIAS MUELLER, Centrum Wiskunde \& Informatica
Random geometric graphs [PDF]
-
If we pick points $X_1,\dots,X_n$ at random from $d$-dimensional space
(i.i.d. according to some probability measure) and fix a $r > 0$,
then we obtain a random geometric graph by joining points by an edge whenever their distance is $< r$.
I will give a brief overview of some of the most important results on random geometric graphs and then describe some of my own work on Hamilton cycles, the chromatic number, the power of two choices and games on random geometric graphs.
- MARIANA OLVERA-CRAVIOTO, Columbia University
Ranking algorithms on trees [PDF]
-
We will present a family of ranking algorithms whose behavior can be described by analyzing the solution to a certain stochastic fixed point equation. One important example is given by Google's PageRank algorithm, which solves a nonhomogeneous linear recursion built on a weighted branching tree. In particular, we show how our techniques allow us to consider algorithms with mixed signed weights, which can be of potential interest in the ranking of opinion or reputation networks.
- PAWEL PRALAT, Ryerson University
Discovery of Nodal Attributes through a Rank-Based Model [PDF]
-
Understanding the relationship between evolving network structures and the attributes of individual network nodes is an important frontier in the study and modeling of self-organizing networks. We propose a rank model of how externally-determined nodal attributes (operationalized as attribute rank relative to other individuals) may change amongst agents over time within a stochastic system. We then propose a model of network self-organization based on this rank model. Finally, we demonstrate how one may make inferences about the attributes of individual nodes when attributes are unobserved, but network structures are readily measured. This approach holds promise to enhance our study of social interactions within the Web graph and in complex social networks in general.
- LADISLAV STACHO, Simon Fraser University
Strong orientations of plane networks [PDF]
-
Directional antennae are widely used in wireless networks not only for reducing energy consumption and interference, but also for improving routing efficiency and security. Caragiannis et al. (2008) were the first to propose the problem of orienting the antennae of a set of sensors in the plane to produce a strongly connected network and compared the range used to the maximum link length of the minimum spanning tree on the set of sensors. I will discuss possible models of the problem, survey known results, and then will concentrate on the case when the transmission range of sensors is not increased (compared to the original omnidirectional antennae range) as well as antennae have spread 0. In this setting the problem reduces to orienting original links of a network to obtain a strongly connected network. We consider this problem with an additional requirement (which was not considered in the literature before); we also want to bound the stretch factor of the new directed network. I will show some proofs of tradeoffs between number of links that need to be oriented and the resulting stretch factor. This is joint work with E. Kranakis an O. Morales.
- CHARALAMPOS TSOURAKAKIS, Carnegie Mellon University
Triangle Counting and Vertex Similarity [PDF]
-
In this talk we will discuss two significant problems of social network analysis: triangle counting and vertex similarity. In the first part of the talk we will present two randomized algorithmic schemes for triangle counting in large-scale graphs, {\em Triangle Sparsifiers} [1,2] and {\em Colorful Triangle Counting} [3] and analyze them using the Kim-Vu concentration theorem and the second moment method respectively. In the second part of the talk, we will present a new way of looking at vertex similarity compared to the existing work. Specifically, we will introduce the concept of {\em Social Network Archetypes} [4] which in combination with appropriate data structures provides us with the ability to answer popular types of queries such as ``which are the $k$ most similar vertices to vertex $v$?''. For both parts of the talk we will
provide an experimental evaluation of our methods. \newline
[1] Tsourakakis, C.E., Kolountzakis, M.N., Miller, G.L.: {\em Triangle Sparsifiers } Journal of Graph Theory and Applications (2011)
[2] Kolountzakis, M.N., Miller, G.L., Peng, R., Tsourakakis, C.E.: {\em Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning.} Internet Mathematics (to appear)
[3] Pagh, R., Tsourakakis, C.: {\em Colorful Triangle Counting and a MapReduce Implementation.} Information Processing Letters (2011)
[4] Tsourakakis, C.E.: {\em Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem.} Arxiv 1110.2813
- RORY WILSON, Dalhousie University
Co-citation used as an estimator of similarity in a geometric model of complex networks [PDF]
-
The spatial preferred attachment (SPA) model is a model for networked information spaces such as domains of the World Wide Web, citation graphs, and on-line social networks. It uses a metric space to model the hidden attributes of the vertices – those vertices that are close in the space share similar characteristics, such as webpage topic, interests or geographical distance. In the model, vertices are elements of a metric space, and link formation depends on the metric distance between vertices.
Through theoretical analysis and simulation, it is shown that for graphs formed according to the SPA model it is possible to infer the metric distance between vertices from the link structure of the graph: the estimate is based on the number of common neighbours of a pair of vertices, the co-citation number. The co-citation method is an early step towards a “reverse engineering” of the model – reconstructing the geometry only through knowledge of the graph properties. This would be a very powerful tool in analyzing networks for which we have only information on the link structure, and not on the nature of the vertices.
- NICK WORMALD, University of Waterloo
On the diameter of the pegging network [PDF]
-
We consider the following process for generating large random graphs. Starting with any given graph, repeatedly add edges that join the midpoints of two randomly chosen edges. This process, which we call the {\em pegging process}, was motivated by a model recently used as a peer-to-peer network. We show that the growing graph is asymptotically very likely to have logarithmic diameter. (Joint work with Stephanie Gerke and Angelika Steger.)
