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) |