Detecting multiple stochastic network motifs in network data

Kai Liu*, William K. Cheung, Jiming Liu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

9 Citations (Scopus)

Abstract

Network motifs are referred to as the interaction patterns that occur significantly more often in a complex network than in the corresponding randomized networks. They have been found effective in characterizing many real-world networks. A number of network motif detection algorithms have been proposed in the literature where the interactions in a motif are mostly assumed to be deterministic, i.e., either present or missing. With the conjecture that the real-world networks are resulted from interaction patterns which should be stochastic in nature, the use of stochastic models is proposed in this paper to achieve more robust motif detection. In particular, we propose the use of a finite mixture model to detect multiple stochastic network motifs. A component-wise expectation maximization (CEM) algorithm is derived for the finite mixture of stochastic network motifs so that both the optimal number of motifs and the motif parameters can be automatically estimated. For performance evaluation, we applied the proposed algorithm to both synthetic networks and a number of online social network data sets and demonstrated that it outperformed the deterministic motif detection algorithm FANMOD as well as the conventional EM algorithm in term of its robustness against noise. Also, how to interpret the detected stochastic network motifs to gain insights on the interaction patterns embedded in the network data is discussed. In addition, the algorithm’s computational complexity and runtime performance are presented for efficiency evaluation.

Original languageEnglish
Pages (from-to)49-74
Number of pages26
JournalKnowledge and Information Systems
Volume42
Issue number1
Early online date29 Aug 2013
DOIs
Publication statusPublished - Jan 2015

Scopus Subject Areas

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence

User-Defined Keywords

  • Expectation maximization algorithms
  • Finite mixture models
  • Social networks
  • Stochastic network motifs

Fingerprint

Dive into the research topics of 'Detecting multiple stochastic network motifs in network data'. Together they form a unique fingerprint.

Cite this