Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Affiliates 
 Visitors 
 Students 
 Research 
 ICAM-LANL 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Colloquia 
 Colloquia Archive 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Archive 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Colloquia 
 
 Jobs 
 Postdocs 
 CNLS Fellowship Application 
 Students 
 Student Program 
 Visitors 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
Thursday, February 24, 2011
1:00 PM - 2:00 PM
CNLS Conference Room (TA-3, Bldg 1690)

Seminar

Random Generative Models for Real Structured Networks

Milan Bradonjic
T5 Los Alamos National Laboratory

The existing probabilistic methods have been most successful in the analysis of unstructured random graph instances that express a large degree of statistical independence. Real-world networks do not always respond well to such existing methods: they have multiscale structure imposed by geometry and other intrinsic correlations among nodes and edges. We developed and analyzed a new structured random generative model, the Geographical Threshold Graph model. This is a node-weighted generalization of Random Geometric Graphs, which more accurately characterizes large scale real-world networks. Nodes are distributed in space, and edges are assigned according to a threshold function involving the distance between nodes and randomly chosen node weights. We show how the structural properties, such as connectedness, diameter, existence and absence of the giant component, clustering coefficient, and chromatic number, as well as mixing time, relate to the threshold value and node weight distribution. These values play an important role not only in theory, but also in applications, such as latency in wireless communications, epidemic spread, or job scheduling. We believe that: (i) our work can can spark further theoretical research in modeling and analysis of structured random networks; (ii) the developed tools will lead to new ways to analyze algorithmic performance, and most excitingly, effective new algorithms on networks.

Host: Humberto C Godinez Vazquez, Mathematical Modeling and Analysis Theoretical Division, 5-9188