Presentation 2021-09-09
On the Effectiveness of Breadth-First Search for Influence Maximization on Unknown Networks
Yuki Wakisaka, Ryotaro Matsuo, Sho Tsugawa, Hiroyuki Ohsaki,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Recently, the influence maximization problem for unknown networks has received much attention. The problem aims to identify a small set of influential nodes only from a partial structure of the network obtained by network sampling. To achieve efficient influence propagation on unknown networks, it is necessary to determine the sampling strategy and the number of sample nodes appropriately. We have analytically clarified the relationship between the sample size and the number of activated nodes when random sampling is used as the sampling strategy through theoretical analysis. In this paper, we extend our previous analysis to derive the expected number of activated nodes when breadth-first search, which is a typical crawl-based sampling strategy, is used. Furthermore, we comparatively investigate the effectiveness of random sampling and breadth-first search in influence maximization for unknown networks through several numerical examples. The results show that sampling with breadth-first search requires a smaller sample size to achieve the same number of activated nodes than random sampling.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Influence Maximization / Information Diffusion / Social Networks / Unknown Networks / Network Sampling / BFS (Breadth-First Search)
Paper # CQ2021-42
Date of Issue 2021-09-02 (CQ)

Conference Information
Committee CQ
Conference Date 2021/9/9(2days)
Place (in Japanese) (See Japanese page)
Place (in English) Online
Topics (in Japanese) (See Japanese page)
Topics (in English) Wireless Communications Quality, 6G, IoT, Resource Management, Wireless Transmission, Cross layer Technologies, etc.
Chair Jun Okamoto(NTT)
Vice Chair Takefumi Hiraguri(Nippon Inst. of Tech.) / Gou Hasegawa(Tohoku Univ.)
Secretary Takefumi Hiraguri(NTT) / Gou Hasegawa(Ritsumeikan Univ.)
Assistant Yoshiaki Nishikawa(NEC) / Ryoichi Kataoka(KDDI Research) / Kimiko Kawashima(NTT)

Paper Information
Registration To Technical Committee on Communication Quality
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) On the Effectiveness of Breadth-First Search for Influence Maximization on Unknown Networks
Sub Title (in English)
Keyword(1) Influence Maximization
Keyword(2) Information Diffusion
Keyword(3) Social Networks
Keyword(4) Unknown Networks
Keyword(5) Network Sampling
Keyword(6) BFS (Breadth-First Search)
1st Author's Name Yuki Wakisaka
1st Author's Affiliation Kwansei Gakuin University(Kwansei Gakuin Univ.)
2nd Author's Name Ryotaro Matsuo
2nd Author's Affiliation Kwansei Gakuin University(Kwansei Gakuin Univ.)
3rd Author's Name Sho Tsugawa
3rd Author's Affiliation University of Tsukuba(Tsukuba Univ.)
4th Author's Name Hiroyuki Ohsaki
4th Author's Affiliation Kwansei Gakuin University(Kwansei Gakuin Univ.)
Date 2021-09-09
Paper # CQ2021-42
Volume (vol) vol.121
Number (no) CQ-173
Page pp.pp.29-34(CQ),
#Pages 6
Date of Issue 2021-09-02 (CQ)