Presentation on theme: "The Universal Laws of Structural Dynamics in Large Graphs Dmitri Krioukov UCSD/CAIDA David Meyer & David Rideout UCSD/Math F. Papadopoulos, M. Kitsak,"— Presentation transcript:
1
The Universal Laws of Structural Dynamics in Large Graphs Dmitri Krioukov UCSD/CAIDA David Meyer & David Rideout UCSD/Math F. Papadopoulos, M. Kitsak, M. Á. Serrano, M. Boguñá M. Ostilli DARPA’s GRAPHS, Washington, DC, Halloween 2012 (Cancelled by the Frankenstorm)
3
Outline Hyperbolic popular similar –Growing random hyperbolic graphs Next step –Random Lorentzian graphs
4
Random geometric graph “Discretization” of a smooth manifolds (B.Riemann, Nature, v.7) Take a circle of radius R Sprinkle N points into it uniformly at random Connect each pair of points iff the distance between them is x r R hyperbolic R grows to R+dR 1 new point in [R,R+dR] new point to existing Growing
6
Connecting to m closest nodes The expected distance to the m’th closest node from t is: New node t located at radial coordinate r t ln t, and connecting to all nodes within distance R t ~ r t, connects to a fixed number of closest nodes
7
Closest nodes New node t connects to a fixed number of existing nodes s with smallest s st The hyperbolic distance between s and t is Find m nodes s, s t, with smallest x st for a given t:
8
Hyperbolic popular similar Two dimensions of attractiveness –Radial popularity: birth time s: The smaller the s, the more popular is the node s –Angular similarity: distance st : The smaller the st, the more similar is the node s to t New node t connects to existing nodes s optimizing trade-offs between popularity and similarity This trade-off optimization yields hyperbolic geometry
9
What else it yields Power-law graphs With strongest possible clustering Effective preferential attachment
11
Clustering Probability of new connections from t to s so far If we smoothen the threshold Then average clustering linearly decreases with T from maximum at T = 0 to zero at T = 1 Clustering is always zero at T > 1 The model becomes identical to PA at T
15
PSO PA PSO PA S, where –PSO is popularity similarity optimization –PA is preferential attachment (popularity) –S is similarity (sphere) PA is 1-dimensional (radial popularity) PSO is d 1-dimensional, where d is the dimensionality of the similarity space
17
Validation Take a series of historical snapshots of a real network Infer angular/similarity coordinates for each node Test if the probability of new connections follows the model theoretical prediction
18
Learning similarity coordinates Take a historical snapshot of a real network Apply a maximum-likelihood estimation method (e.g., MCMC) using the static hyperbolic model Metropolis-Hastings example –Assign random coordinates to all nodes –Compute current likelihood –Select a random node –Move it to a new random angular coordinate –Compute new likelihood L n –If L n > L c, accept the move –If not, accept it with probability L n / L c –Repeat
19
Real networks PGP web of trust –Nodes: PGP certificates (roughly, people) –Links: Trust relationships Internet –Nodes: Autonomous systems (ASes) –Links: Business relationships Metabolic (E.coli) –Nodes: Metabolites –Links: Reactions
28
Normalized likelihood The popularity similarity model does not describe well the actor network because very dissimilar actors often collaborate on big movies
32
Capturing network structure As a “simple” consequence of the fact the PSO model accurately describes the large-scale network growth dynamics, it also reproduces very well the observed large-scale network structure across a wide range of structural properties
36
Take-home messages (on PSO) Popularity similarity optimization dynamics Geometrical hyperbolicity Topological heterogeneity transitivity (real nets) Popularity is modeled by radial coordinates Similarity is modeled by angular coordinates –Projections of a properly weighted combination of all the factors shaping the network structure
37
Immediate applications (submitted) New simple network-embedding method –The idea is to “replay” the growth of a given network snapshot according to PSO New link prediction method, outperforming all the most popular link prediction methods –Some classes of links can be predicted with 100% accuracy –Perhaps because the method captures all the factors shaping the network structure
39
Plausible solution Geometry under real networks is not hyperbolic but Lorentzian Lorentzian manifolds explicitly model time Proof that PSO graphs are random geometric graphs on de Sitter spacetime (accepted)
44
Alexandrov sets Form a base of the manifold topology –Similar to open balls in Riemannian case
45
Random geometric graph “Discretization” of a smooth manifolds (B.Riemann, Nature, v.7) Take a circle of radius R Sprinkle N points into it uniformly at random Connect each pair of points iff the distance between them is x r R Lorentzian 0; because Alexandrov sets are “balls” now
47
Major challenge (in progress) On the one hand, random Lorentzian graphs are random geometric graphs, and consequently exponential random graphs (equilibrium ensembles) On the other hand, they are dynamic growing graphs (non-equilibrium ensembles) Can it be the case that a given ensemble of graphs is static (equilibrium) and dynamic (non-equilibrium) at the same time??? If we prove that it is indeed the case, then we –Discover some unseen static-dynamic graph duality –Open a possibility to apply very powerful tools developed for equilibrium systems (e.g., exponential random graphs), to dynamic networks
48
F. Papadopoulos, M. Kitsak, M. Á. Serrano, M. Boguñá, and D. Krioukov, Popularity versus Similarity in Growing Networks, Nature, v.489, p.537, 2012
To make this website work, we log user data and share it with processors. To use this website, you must agree to our Privacy Policy, including cookie policy.
