IEICE TRANSACTIONS on Communications
Information Propagation Analysis of Social Network Using the Universality of Random Matrix
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.
- 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
Authors
Yusuke SAKUMOTO
Tokyo Metropolitan University
Tsukasa KAMEYAMA
Nochu Information System Co., Ltd
Chisa TAKANO
Hiroshima City University
Masaki AIDA
Tokyo Metropolitan University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yusuke SAKUMOTO, Tsukasa KAMEYAMA, Chisa TAKANO, Masaki AIDA, "Information Propagation Analysis of Social Network Using the Universality of Random Matrix" in IEICE TRANSACTIONS on Communications,
vol. E102-B, no. 2, pp. 391-399, February 2019, doi: 10.1587/transcom.2018EBP3098.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2018EBP3098/_p
Copy
@ARTICLE{e102-b_2_391,
author={Yusuke SAKUMOTO, Tsukasa KAMEYAMA, Chisa TAKANO, Masaki AIDA, },
journal={IEICE TRANSACTIONS on Communications},
title={Information Propagation Analysis of Social Network Using the Universality of Random Matrix},
year={2019},
volume={E102-B},
number={2},
pages={391-399},
abstract={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.},
keywords={},
doi={10.1587/transcom.2018EBP3098},
ISSN={1745-1345},
month={February},}
Copy
TY - JOUR
TI - Information Propagation Analysis of Social Network Using the Universality of Random Matrix
T2 - IEICE TRANSACTIONS on Communications
SP - 391
EP - 399
AU - Yusuke SAKUMOTO
AU - Tsukasa KAMEYAMA
AU - Chisa TAKANO
AU - Masaki AIDA
PY - 2019
DO - 10.1587/transcom.2018EBP3098
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E102-B
IS - 2
JA - IEICE TRANSACTIONS on Communications
Y1 - February 2019
AB - 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.
ER -
English
