Computational and Mathematical Methods in Medicine
Volume 2012 (2012), Article ID 910380, 12 pages
Research Article

An Analytical Approach to Network Motif Detection in Samples of Networks with Pairwise Different Vertex Labels

1Institute of Medical Statistics, Computer Sciences and Documentation, Jena University Hospital, Friedrich Schiller University Jena, Bachstrasse 18, 07743 Jena, Germany
2Department of Biological and Clinical Psychology, Friedrich Schiller University Jena, Am Steiger 3, Haus 1, 07743 Jena, Germany
3Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Fakultät IV, Elektrotechnik und Informatik, Sekr. FR 6-1, Franklinstrasse 28/29, 10587 Berlin, Germany

Received 10 November 2011; Revised 17 January 2012; Accepted 6 February 2012

Academic Editor: Mingzhou Ding

Copyright © 2012 Christoph Schmidt et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Network motifs, overrepresented small local connection patterns, are assumed to act as functional meaningful building blocks of a network and, therefore, received considerable attention for being useful for understanding design principles and functioning of networks. We present an extension of the original approach to network motif detection in single, directed networks without vertex labeling to the case of a sample of directed networks with pairwise different vertex labels. A characteristic feature of this approach to network motif detection is that subnetwork counts are derived from the whole sample and the statistical tests are adjusted accordingly to assign significance to the counts. The associated computations are efficient since no simulations of random networks are involved. The motifs obtained by this approach also comprise the vertex labeling and its associated information and are characteristic of the sample. Finally, we apply this approach to describe the intricate topology of a sample of vertex-labeled networks which originate from a previous EEG study, where the processing of painful intracutaneous electrical stimuli and directed interactions within the neuromatrix of pain in patients with major depression and healthy controls was investigated. We demonstrate that the presented approach yields characteristic patterns of directed interactions while preserving their important topological information and omitting less relevant interactions.