Motifs, coherent configurations and second order network generation

DOI10.1016/J.PHYSD.2021.133116MaRDI QIDQ2670211zbMATH OpenOpenAlexFDO

Authors Jared C. Bronski, Timothy Ferguson

Publication date 10 March 2022

Published in Physica D (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.05076

zbMATH Keywords

coherent configurationsrandom networksstatistical models

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: In this paper we illuminate some algebraic-combinatorial structure underlying the second order networks (SONETS) random graph model of Nykamp, Zhao and collaborators. In particular we show that this algorithm is deeply connected with a certain homogeneous coherent configuration, a non-commuting generalization of the classical Johnson scheme. This algebraic structure underlies certain surprising identities (that do not appear to have been previously observed) satisfied by the covariance matrices in the Nykamp-Zhao scheme. We show that an understanding of this algebraic structure leads to simplified numerical methods for carrying out the linear algebra required to implement the SONETS algorithm. We also show that this structure extends naturally to the problem of generating random subgraphs of graphs other than the complete directed graph.

Review text

This paper studies the generation of second-order random networks, where not only the edge probabilities but also the two edge motifs have probabilities independently to appear. The model is constructed as follows. First generate a Gaussian random vector \(\omega\in\mathbb{R}^E\), where \(E=N(N-1)\) and \(N\) is the number of nodes. An edge \(\epsilon\) is present if \(\omega_{\epsilon}>x\) and absent if \(\omega_{\epsilon}\le x\) for some threshold \(x\). Some two edge graphs are defined as motifs as follows. It is reciprocal if the edges point between the same pair of nodes in opposite directions. It is convergent if both edges point inwards to a common node. It is divergent if both edges point outward from a common node. It is a chain if one edge points inward to a node and the other points outward from the same node. The covariance matrix of \(\omega\) is then defined based on these four types. This gives a random graph model with fixed edge probabilities and edges appear with certain correlations determined by the covariance matrix. An undirected version of the second-order network model is given, which is connected to the Johnson scheme. The paper presents some concrete examples for the random network generation based on such a model. Some underlying algebraic properties of this model have also been discussed.

Recommendations

• Network motifs: mean and variance for the count
• Motifs for processes on networks
• Statistical properties of a generalized threshold network model
• A uniform random graph model for directed acyclic networks and its effect on motif-finding
• Random graph generation using multiple switches of edges

Cites work

• A random graph model for massive graphs
• A Scalable Generative Graph Model with Community Structure
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• Association schemes and coding theory
• CLASSIFICATION OF ASSOCIATION SCHEMES WITH 16 AND 17 VERTICES
• Coherent configurations. I: Ordinary representation theory
• Collective dynamics of `small-world' networks
• Communities in Networks
• Dynamical changes in neurons during seizures determine tonic to clonic shift
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 1234590 (Why is no real title available?)
• scientific article; zbMATH DE number 1981748 (Why is no real title available?)
• scientific article; zbMATH DE number 2117211 (Why is no real title available?)
• Investigating the correlation-firing rate relationship in heterogeneous recurrent networks
• Kronecker graphs: an approach to modeling networks
• Motif statistics and spike correlations in neuronal networks
• On a representation of the Verhulst logistic map
• Predicting neural network dynamics via graphical analysis
• Renormalization group analysis of the small-world network model
• Scalable and exact sampling method for probabilistic generative graph models
• Scale-free networks: a decade and beyond
• Statistical mechanics of complex networks
• The Spectra of Random Graphs with Given Expected Degrees
• Theory of Association Schemes

Cited in

(1)

• A motif building process for simulating random networks

This page was built for publication: Motifs, coherent configurations and second order network generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670211)