Discovering Colored Network Motifs

Pedro Ribeiro and Fernando Silva

2014

Abstract

Network motifs are small overrepresented patterns that have been used successfully to characterize complex networks. Current algorithmic approaches focus essentially on pure topology and disregard node and edge nature. However, it is often the case that nodes and edges can also be classified and separated into different classes. This kind of networks can be modeled by colored (or labeled) graphs and in this paper we present a definition of a colored motif and an algorithm that efficiently discovers this kind of motifs. We use g-tries, a specialized data-structure created for finding sets of subgraphs. G-Tries encapsulate common sub-structure, and with the aid of symmetry breaking conditions and a customized canonization methodology, we are able to efficiently search for several colored patterns at the same time. We apply our algorithm to a set of representative complex networks, showing that we can find colored motifs, outperforming previous methods.

Keywords

Network motifs; colored motifs; vertex color; edge color

Reference (text)

Pedro Ribeiro and Fernando Silva. Discovering Colored Network Motifs. Proceedings of the 5th International Workshop on Complex Networks (CompleNet), Vol. 549, pp. 107-118, Springer SCI, Bologna, Italy, March, 2014.

Bibtex

@inproceedings{ribeiro-COMPLENET2014,
  author = {Pedro Ribeiro and Fernando Silva},
  title = {Discovering Colored Network Motifs},
  doi = {10.1007/978-3-319-05401-8_11},
  booktitle = {5th International Workshop on Complex Networks},
  volume = {549},
  pages = {107-118},
  publisher = {Springer SCI},
  month = {March},
  year = {2014}
}