Motifs, coherent configurations and second order network generation (Q2670211)

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.