Skip to Content
[CAIDA - Center for Applied Internet Data Analysis logo]
Center for Applied Internet Data Analysis
www.caida.org > funding : ulsd-darpa
Universal Laws of Structural Dynamics of Large Scale Graphs
Sponsored by:
Defense Advanced Research Projects Agency (DARPA)
The main goal of this project is to develop a mathematically rigorous model describing dynamic graphs of complex networks evolving in time.

Funding source: DARPA grant HR0011-12-1-0012. Period of performance: September 10, 2012 - September 9, 2013.

|   Statement of Work     Proposal   |

Statement of Work

Many different real networks exhibit certain structural similarities, suggesting that there is a possible universal explanation for their common structure. Previously, we developed a powerful and unique theory that employed hyperbolic geometry to explain the ubiquitous common structure of complex networks, and to linking this structure to the optimality of their common functions. Yet, the main limitation of this theory is that from the mathematical perspective, it rigorously applies only to static graphs.

To detect anomalies, to predict network behavior, we need a mathematically rigorous theory for dynamic graphs that grow and evolve. We propose to make the first step towards developing such a theory by mapping our hyperbolic model of complex networks to pseudo-Riemannian geometry. Pseudo-Riemannian geometry is the geometry of manifolds, in which one coordinate can be associated with time, making this geometry a perfect candidate to model graphs evolving in time. Therefore, the main premise that we set to prove during the first year of this project is that random geometric graphs built on top of Lorentzian manifolds (a well-studied class of pseudo-Riemannian manifolds) model the dynamical properties of large real networks.

We will accomplish the following tasks (see the complete proposal for term definitions and details):

Task 1: Find a Lorentzian manifold M such that there exist bijection Φ between M and hyperbolic space H that preserves the volume form, and maps Alexandrov sets in M to intersections of balls in H (Sep 2012 - Feb 2013)

1.1Prepare a candidate list of manifolds
1.2For each manifold in the list, introduce a coordinate system (a spherical foliation of the manifold).
1.3Find the radial coordinate in H as the function of time in M.
1.4If the solution in 1.3 exists, prove that it is invariant under the group of isometries of M and H.

Task 2: Derive the structural properties of random geometric graphs built on top of the selected manifold (Mar 2013 - May 2013)

2.1Generate random geometric graphs on M.
2.2Compute the volumes of a selected compact patch in M and Alexandrov sets in it.
2.3Derive analytically the graph size, average degree, degree distribution, clustering.

Task 3: Derive the dynamical properties of the graphs generated in Task 2 (Apr 2013 - Jun 2013)

Task 4: Validate the analytic results in numeric experiments (May 2013 - Jul 2013)

4.1Implement the graph model in software.
4.2Simulate the graphs and compute their structural and dynamic properties.
4.3Compare the simulated properties to the theoretical predictions.

Task 5: Apply the obtained results to real networks (Mar 2013 - Aug 2013)

5.1Collect real network data.
5.2Process the data extracting the structural and dynamic properties of interest for real graphs.
5.3Investigate how accurately the theoretical and numerical results describe the real graphs.

The main impact and practical significance of the proposed work is that the knowledge of the universal laws governing the dynamics of complex networks will allow us to predict network behavior, while abnormal dynamics deviating from such laws will then signify anomalous activity.

Deliverables

UCSD researchers perform fundamental research on a reasonable efforts basis.

#Deliverable DescriptionTypeDue date
1Manifold and mappingwritten reportFeb 2013
2Graph modeling simulation softwaresoftwareJun 2013
3Structural and dynamical characteristics of real networksdataJul 2013
4Final reportwritten reportAug 2013

Future Work

If our first-year tasks are successfully completed, then in subsequent years we will propose to:

  1. identify the equations describing the dynamics of random geometric graphs in the resulting model;
  2. develop a set of tools and methods, based on these equations, to predict network dynamics and detect anomalies;
  3. apply the developed methods to real networks.
  Last Modified: Mon Jan-7-2013 15:19:25 PST
  Page URL: http://www.caida.org/funding/ulsd-darpa/index.xml