Title: Spatial Peer-to-Peer Networks
We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model allows one to cope with the fact that distant peers often have a smaller rate than nearby peers. We show that the spatial point process describing peers in their steady state then exhibits an interesting repulsion phenomenon.
We study the implications of this phenomenon by analyzing two asymptotic regimes of the peer-to-peer network: the fluid regime and the hard-core regime. We get closed form expressions for the mean (and in some cases the law) of the peer latency and the download rate obtained by a peer as well as for the spatial density of peers in the steady state of eachregime. The analytical results are based on a mix of stochastic and dimensional analysis and have important design implications.
Title: Complex Information Systems
The talk will provide an overview of complex information systems including quantifying, managing, and designing heterogeneous networked systems. Methods of measuring and assessing the performance of networked, software, and hardware integrated systems such as cloud architectures will be discussed including techniques of sparse approximation in systems measurements, and algebraic and topological statistical metrics for performance. Strategies of quantifying risk over different geometric and statistical classes of distributed systems will be examined as well as methods of tracking and coding dynamic information flows.
Title: Mining Big Data in Disconnected Networks
In this talk, we would like to address the notions of large-scale random networks, connectivity and resilience, from a different angle. The goal is to start a discussion about other topics where analysis of large networks can be relevant. We believe that a big challenge lies in building applications that allow one to extract utility from personal information available in various forms through social networking and crowdsourced services. As opposed to current practice we wish to provide users with the ability to disconnect and release their information as they wish, which sometimes can be within the context of an economic transaction. The main technical challenge that we will discuss in this talk is how it motivates new approach to data mining that leads to simpler algorithms that are more scalable and private, and motivates new problems in random network.
Title: Graph Geometry adapted to Signal Processing of Observations on Networks
We will provide an overview of methodologies to build graphs on networks tuned to respond to classes of queries.
The goal is to devise metrics on the network so that the queries are as smooth or predictable as possible,(nearest neighbors algorithms work).
In particular we relate ideas from Harmonic Analysis, Signal processing, Geometry, to various Machine Learning methods and goals, and will illustrate on financial data, and psychological profiles.
Title: Percolation in Directed Random Geometric Graphs
The connectivity graph of wireless networks, under many models as well as in practice, may contain unidirectional links. The simplifying assumption that such links are useless is often made, mainly because most wireless protocols use per-hop acknowledgments. However, two-way communication between a pair of nodes can be established as soon as there exists paths in both directions between them. Therefore, instead of discarding unidirectional links, one might be interested in studying the strongly connected components of the connectivity graph.
In this presentation, we look at two directed random geometric graph models, which are extensions of popular (undirected) models for wireless networks. We will show that indeed, a giant strongly connected component appears at a lower node density if one takes unidirectional links into account. Also, we show that the density at which this happens is in fact the same as the critical density for directed percolation.
Title: The Science of Cybersecurity
This talk will discuss newly initiated research at the Army Research Laboratory related to computer security, focused on the science of cybersecurity. The fundamental goal of the majority of the research revolves around the science of intrusion detection. The goal of the science of cybersecurity research is to develop foundational knowledge that will lead to the development of novel techniques capable of dealing with real-world cybersecurity scenarios of the future, e.g., advanced persistent threats. Future cybersecurity scenarios will necessitate moving away from strictly signature and pattern based detection techniques. Internally, specific projects Dr. Erbacher is working on include:
Title: A Flexible Modeling Approach: Abstract Geometric Random Graphs
Large-scale, random wireless network topologies are often modeled by geometric random graphs, also known as random unit disk graphs. While this model is amenable to analysis, it is often a rather simplis Cornell Universitytic reflection of a wireless network topology. We extend the model to incorporate more sophisticated conditions. Examples include obstacles to radio propagation, non-uniform and non-independent node distributions, traffic load, and various other extra conditions that can easily destroy the tractability of the random unit disk graph model. We show that such complex conditions can still be naturally incorporated in our abstract geometric random graph model.
Furthermore, we demonstrate that despite the high level of generality, it is still possible to prove nontrivial properties about asymptotic connectivity in our model. We also demonstrate that our approach provides a flexible analysis tool in situations where the analysis of the network topology under the complex conditions would be very hard to carry out directly.
Title: Stochastic Routing
Broadcast is a fundamental operation in networks, especially in wireless Mobile Ad Hoc NETworks (MANET). For example, some form of broadcasting is used by all on-demand MANET routing protocols, when there is uncertainty as to the location of the destination node, or for service discovery. Being such a basic operation of the networking protocols, the importance of efficient broadcasting, especially in large-scale networks, has long been recognized by the networking community. Numerous papers proposed increasingly more efficient implementation of broadcasting, while other studies presented bounds on broadcast performance. In this talk, we present a new scalable approach to efficient broadcast in networks with dynamic topologies, such as MANET, and we introduce a new broadcasting algorithm for such networking environments. We present the evaluation of the proposed algorithm, showing that its performance comes remarkably close to the corresponding theoretical performance bounds. Furthermore, we compare the performance of the proposed algorithm with other recently proposed schemes, especially in the context of various mobility settings.
Title: On Random Threshold Graphs
Following the work of Barabasi and Albert, the scale free nature of complex networks (understood as its degree distribution being power law) is often explained by growth models with a preferential attachment mechanism. Although in some contexts preferential attachment is a reasonable assumption, it is predicated on the degree of each vertex being available to newly added nodes, either explicitly or implicitly. There are many situations where this assumption is questionable, and where instead the creation of a link between two nodes results in a mutual benefit based on their intrinsic attributes, e.g., authority, friendship, social success, strength of interaction, etc.
Random threshold graph models incorporate this viewpoint in the establishment of links. Interest in them has been spurred in part by the following recent finding: Scale-free networks can arise without having to invoke a preferential attachment mechanism. With this in mind, we explore various scaling properties for random threshold graphs in the many node regime. We provide a complete characterization for the underlying zero-one laws for graph connectivity, and in each case we identify the corresponding critical scalings. These results are by-products of well-known facts in Extreme Value Theory concerning the asymptotic behavior of running maxima on i.i.d. rvs. In one important special case we are able to show that the scalings ensuring a power-law degree distribution will not result in graph connectivity in the asymptotically almost sure (a.a.s.) sense.
This is joint work with former Ph.D. student Osman Yagan, now a postdoc with CyLab at CMU.
Title: Bootstrap Percolation on Random Geometric Graphs
Random geometric graphs provide an appropriate model for percolation in settings where the neighborhood structure of each node is determined by geographical distance, as in wireless ad hoc and sensor networks as well as in contagion. We study bootstrap percolation on random geometric graphs in the regime when the graph is (almost surely) connected and activation of nodes is contingent on having "theta" active nodes in the immediate neighborhood. We derive tight asymptotic bounds on the critical threshold, p_c(theta), such that for all p > p_c(theta) full percolation takes place whp, whereas for p < p_c(theta) it does not. We conclude with simulations that compare numerical thresholds with those obtained analytically.
This is joint work with Milan Bradonjic.
Title: Coverage and Percolation in Random Geometric Graphs
For classical random graphs, the vertex set is fixed and finite, and the edges are inserted randomly. For random geometric graphs, the vertices are randomly located in space, and the edges are then inserted using some deterministic rule. A simple example is the Gilbert model, in which two vertices are joined if they lie within distance r of each other. A more complicated example is the secrecy graph model of a secure wireless network, introduced by Martin Haenggi in 2008. For many such graphs, there is also a related coverage process: for instance, corresponding to the Gilbert model, we place a solid ball of radius r/2 around each randomly placed vertex. I'll discuss some recent results on such coverage processes, and on percolation in the underlying random graphs.
This is joint work with Paul Balister, Bela Bollobas, Martin Haenggi and Mark Walters.
Title: Resilience of PCA Analysis
PCA analysis is a crucial tool in studying large data and network. In this analysis, one wants to project a large matrix onto the subspace spanned by the first few singular vectors.
The question we would like to consider is the resilience of this space with respect to random noise. If the data matrix is perturbed by some random noise, will it have a large impact on the position of the subspace?
Title: Power Grid Vulnerability to Geographically Correlated Failures
In this talk, we consider power line outages in the transmission system of the power grid, and specifically those caused by a natural disaster or a large scale physical attack. We present an analytical model of such geographically correlated failures, investigate the model's properties, and show that it differs from other models used to analyze cascades in the power grid. We then show how to identify the most vulnerable locations in the grid and perform extensive numerical experiments with real grid data to investigate the various effects of geographically correlated outages and the resulting cascades.
Joint work with Andrey Bernstein (Technion), Daniel Bienstock (Columbia University), David Hay (Hebrew University), and Meric Uzunoglu (Columbia University)
Previous: Program
Workshop Index
DIMACS Homepage