Large motifs in homogeneous networks

Abstract: A graph is termed to be homogeneous if the degrees and the co-degrees (the number of common neighbors of a pair of vertices) are approximately the same throughout the graph. In this talk, we will discuss the existence and the number of isomorphic copies of subgraphs in large homogeneous graphs. Under the assumption that in a homogeneous graph on \(n\) vertices the degrees and the co-degrees are close to \(np\) and \(np^2\), respectively, with an error of at most \(O(n^\delta)\), for some \(p \in (0,1)\) and \(\delta \in [0,1)\), we will show that for some constant \(C_\delta >0\), depending only on \(\delta\), the number of isomorphic copies of any subgraph of (vertex) size at most \(C_\delta \log n /\log(1/p)\) is asymptotically same as that of an Erd\({o}\)s-R\('{e}\)nyi graph with edge connectivity probability \(p\). The constant \(C_\delta\) will be shown to be optimal. This result is applicable to a wide class of graphs including but not limited to Exponential Random Graph Models, threshold graphs from high-dimensional correlation networks, and Erd\({o}\)s-R\('{e}\)nyi graphs conditioned on large cliques.

The talk is based on a joint work with Shankar Bhamidi, Suman Chakraborty, and Andrew Nobel.