Title: Models and Tools for Large Graphs with Imposed Structural Properties
Speaker: Milan Bradonjic, Mathematical Modeling and Analysis Group, and Center for Nonlinear Studies Los Alamos National Laboratory
Date: Friday, January 23, 2009 11:00 - 12:00 pm
Location: DyDAn Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We will focus on theoretical issues of modeling and solving problems on real-world networks where computational intractability limits our current analysis capabilities. We provide a combinatorial analysis of a static generative random graph model for networks, which includes both geometric information and node weight information (Geographical Threshold Graphs). We derive conditions and bounds for the absence and existence of the giant component, as well as for connectivity, bounds on diameter, and give an explicit expression for the clustering coefficient. We also analyze a coloring algorithm together with the clique number, in order to derive bounds on the chromatic number. Applications of the model range from wireless networks to social networks: in cases such as wireless, social or epidemics networks, weights may represent power, attractiveness or susceptibility, respectively. We believe that our model (or its extension) can spark further theoretical research on the prediction of social phenomena that requires a far better understanding of processes such as: creation and growth of social networks, epidemics spread and formation of economic networks.
See our new DIMACS/DyDAn Multidisciplinary Seminar Series
Back to DyDAn Home Page
Back to DIMACS Home Page