| 講演抄録／キーワード |
| 講演名 |
2019-10-03 11:15
［ポスター講演］グラフ上の影響伝搬におけるランダムサンプリングの効率性に関する検討
○脇坂悠生・山下量之（関西学院大）・津川 翔（筑波大）・大崎博之（関西学院大） |
| 抄録 |
（和） |
近年、口コミマーケティング等への応用の期待から、ソーシャルネットワークにおける影響最大化問題が活発に研究されている。影響伝搬問題は、あるグラフにおいて、
影響最大化するような少数のシードノードを決定するという、グラフ上の組合せ
最適化問題として定式化できる。一般に、ソーシャルネットワークのような
大規模ネットワーク全体のトポロジ構造を取得することは容易ではないため、
ネットワークサンプリングによって得られた部分的なソーシャルネットワークのみの
情報から、影響力の高いシードノードを決定するという問題が検討されている。
ネットワークのトポロジが未知であるようなネットワークにおいて効率的な影響伝搬を
実現するためには、ソーシャルネットワークの一部をネットワークサンプリングに
よって部分的に取得する上で、サンプルノード数を適切に決定しなければならない。
本研究では、数学的解析により、トポロジ構造が不明であるような
大規模ネットワークにおいて、ランダムなノードサンプリングと次数順
にシードノードを選択するという
基本的なアルゴリズムを用いた時の、ランダムサンプリングのサンプル数と
影響伝搬による被影響ノード数の期待値の関係を調査する。 |
| （英） |
Influence maximization in a social network has been intensively studied,
motivated by its application to so-called viral marketing. The
influence maximization problem is formulated as a combinatorial
optimization problem on a graph that aims to identify a small set of
influential nodes (i.e., seed nodes) such that the expected size of
the influence cascade triggered by the seed nodes is maximized.
In general, it is difficult in practice to obtain the
complete knowledge on large-scale social networks.
Therefore, a problem of identifying a set of
influential seed nodes only from a partial structure of the
social network obtained from network sampling strategies
has also been studied in recent years.
To achieve efficient influence propagation in unknown networks,
the number of sample nodes must be determined appropriately for
obtaining a partial structure of the social network. In this
research, assuming that the random sampling strategy
is used for obtaining the partial structure of a large-scale network,
and seed nodes are determined based on their degree, we investigate
the relation between the sample size and the expected size of
influence cascade triggered by the seed nodes through
theoretical analyses. |
| キーワード |
（和） |
影響最大化 / 複雑ネットワーク / ソーシャルネットワーク / ネットワークサンプリング / 情報拡散 / / / |
| （英） |
Influence Maximization / Complex Networks / Social Networks / Graph Sampling / Information Diffusion / / / |
| 文献情報 |
信学技報 |
| 資料番号 |
|
| 発行日 |
|
| ISSN |
|
| PDFダウンロード |
|