How to model very large graphs

Title: How to model very large graphs

SpeakerProfessor Santosh S. Vempala, GeorgiaTech Institute of Technology

 
Date: Friday, 22nd February 2019
Time: 2 pm
Venue: LH1, ELC, NCBS Bangalore

 

Abstract:

A wide variety of complex networks (social, biological, information etc.) exhibit local clustering with substantial variation in the clustering coefficient (the probability of neighbors being connected). Existing models of large graphs capture power law degree distributions and small-world properties, but only limited clustering behavior. We introduce a generalization of the classical Erdõs-Rényi model of random graphs which provably achieves a wide range of desired clustering coefficient, triangle-to-edge and four-cycle-to-edge ratios for any given graph size and edge density. Rather than choosing edges independently at random, in the Random Overlapping Communities model, a graph is generated by choosinga set of random, relatively dense subgraphs ("communities"). We discuss the explanatory power of the model and some of its consequences, including convergence of a sequeceof sparse graphs in terms of moments of the graph's spectrum (equivalent to the numbers of closed k-walks) appropriately normalized; such properties probably cannot be captured by popular stochastic block models. This is joint work with Samantha Petti. We will use connectome as a running example.

© Copyright 2016 - 2018 National Centre for Biological Sciences