Network motifs detection using random networks with prescribed subgraph frequencies Miguel Silva, Pedro Paredes and Pedro Ribeiro 2017

Abstract

In order to detect network motifs we need to evaluate the exceptionality of subgraphs in a given network. This is usually done by comparing subgraph frequencies on both the original and an ensemble of random networks keeping certain structural properties. The classical null model implies preserving the degree sequence. In this paper our focus is on a richer model that approximately fixes the frequency of subgraphs of size K−1 to compute motifs of size K. We propose a method for generating random graphs under this model, and we provide algorithms for its efficient computation. We show empirical results of our proposed methodology on neurobiological networks, showcasing its efficiency and its differences when comparing to the traditional null model.

Keywords

Network Motifs; Random Graphs; Subgraph Counting

Digital Object Identifier (DOI)

doi 10.1007/978-3-319-54241-6_2

Publication in PDF format

pdf Download PDF

Software

software GenK - Graph Generator

Journal/Conference/Book

8th Conference on Complex Networks

Reference (text)

Miguel Silva, Pedro Paredes and Pedro Ribeiro. Network motifs detection using random networks with prescribed subgraph frequencies. Proceedings of the 8th Conference on Complex Networks (CompleNet), pp. 17-29, Springer, Dubrovnik, Croatia, March, 2017.

Bibtex

@inproceedings{ribeiro-COMPLENET2017,
  author = {Miguel Silva and  Pedro Paredes and Pedro Ribeiro},
  title = {Network motifs detection using random networks with prescribed subgraph frequencies},
  doi = {10.1007/978-3-319-54241-6_2},
  booktitle = {8th Conference on Complex Networks},
  pages = {17-29},
  publisher = {Springer},
  month = {March},
  year = {2017}
}