Information Propagation Analysis of Social Network Using the Universality of Random Matrix

Yusuke SAKUMOTO
Tsukasa KAMEYAMA
Chisa TAKANO
Masaki AIDA

Publication
IEICE TRANSACTIONS on Communications   Vol.E102-B    No.2    pp.391-399
Publication Date: 2019/02/01
Publicized: 2018/08/17
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2018EBP3098
Type of Manuscript: PAPER
Category: Multimedia Systems for Communications
Keyword: 
social network,  information propagation,  random matrix,  spectral graph theory,  Wigner semicircle law,  Laplacian matrix,  

Full Text: PDF>>
Buy this Article


Summary: 
Spectral graph theory gives an algebraic approach to the analysis of the dynamics of a network by using the matrix that represents the network structure. However, it is not easy for social networks to apply the spectral graph theory because the matrix elements cannot be given exactly to represent the structure of a social network. The matrix element should be set on the basis of the relationship between persons, but the relationship cannot be quantified accurately from obtainable data (e.g., call history and chat history). To get around this problem, we utilize the universality of random matrices with the feature of social networks. As such a random matrix, we use the normalized Laplacian matrix for a network where link weights are randomly given. In this paper, we first clarify that the universality (i.e., the Wigner semicircle law) of the normalized Laplacian matrix appears in the eigenvalue frequency distribution regardless of the link weight distribution. Then, we analyze the information propagation speed by using the spectral graph theory and the universality of the normalized Laplacian matrix. As a result, we show that the worst-case speed of the information propagation changes up to twice if the structure (i.e., relationship among people) of a social network changes.