Geometry of Dynamic Large Networks: A Scaling and Renormalization Group Approach
Abstract
The research conducted during the period of performance of this grant concerned investigation of large-scale geometry of prototypical and real-life large graphs, and their analytical/numeric estimation of their core congestion. The research included demonstration of delta-hyperbolicity in a large variety of communication and social networks via scaling of the curvature plots through renormalization, detection of graph bottlenecks using a novel techniques based on the Dirichlet eigenvectors of the (normalized) graph Laplacian, proof of the fact that remetrization (by factors away from zero and infinity) does not eliminate O(N sq) core congestion in delta-hyperbolic graphs, derivation of an analytical expression for the average nodal congestion involving the sum of the inverses of the non-zero eigenvalues of the graph Laplacian when random walk routing replaces geodesic routing, and finally determination of the threshold for bootstrap percolation in periodic trees as an upper bounding mechanism for the threshold for more general graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 11, 2013
- Accession Number
- ADA595914
Entities
People
- Iraj Saniee
- Onuttom Narayan