TY - JOUR
T1 - Detecting multiple stochastic network motifs in network data
AU - Liu, Kai
AU - Cheung, William K.
AU - Liu, Jiming
N1 - Funding information:
This work was supported by the General Research Fund (HKBU210410) from the Research Grant Council of the Hong Kong Special Administrative Region, China.
Publisher copyright:
©Springer-Verlag London 2013
PY - 2015/1
Y1 - 2015/1
N2 - 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.
AB - 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.
KW - Expectation maximization algorithms
KW - Finite mixture models
KW - Social networks
KW - Stochastic network motifs
UR - http://www.scopus.com/inward/record.url?scp=84957964666&partnerID=8YFLogxK
U2 - 10.1007/s10115-013-0680-4
DO - 10.1007/s10115-013-0680-4
M3 - Journal article
AN - SCOPUS:84957964666
SN - 0219-1377
VL - 42
SP - 49
EP - 74
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
IS - 1
ER -