テンポラルネットワークによる集団の合意形成
久保鮎乃1(指導教員：工藤和恵)

はじめにされた平均距離を d と定義する。

N i−1

1 ∑ ∑22d≡[x(t)−x(t)]ij2σ 2 N (N − 1)

テンポラルネットワークとは、リンクに時刻情報を含むネットワークであり、近年テンポラルネットワークの解析が急速に進められてきている [1]。個人間の会話のネットワークを考えると、時刻情報のないネットワークとは異なり、リンクは会話が行われるその一瞬だけ使われることになる。先行研究 [2] によると、ネットワーク上の社会的ダイナミクスは、どのペアが先に会話しどのペアが後に会話するかによって合意形成が加速または減速する場合がある。本研究では、ネットワーク内のリンクが使用される順番をリンクオーダーと呼び、合意形成の速度に与える影響を検証する。

23モデル

表 1: 時間情報なしネットワークデータ
ネットワーク(1)(2)

この期間中、他の N − 2 ノードの状態は更新されない。リンク (i, j) 適用後の状態 xi (τ ), xj (τ ) は、リンク適用前の状態 xi (0), xj (0) に関して以下のように与えられる。
() ()()
1+e−2τ
1−e−2τ
xi (τ )
xi (0)
22=1+e−2τ
1−e−2τ
xj (τ )
xj (0)
22(3)したがって、次のように書ける。

x(τ ) = exp(−L(ij) τ )x(0) = (I − εL(ij) )x(0)

結果と考察

KONECT(http://konect.uni-koblenz.de) からダウンロードした時間情報なしのデータと時間情報ありのネットワークについてそれぞれ d を計算し、比較を行った。
まず、時間情報なしのネットワーク karate、dolphins,zebra について d を計算した。この 3 つのネットワー
クは、ノードは一個体、リンクは個体同士の交流関係を表すものである。ネットワークの性質となる数値がd 値に影響すると考えそれぞれのネットワークの特徴量を計算した [3]。それをまとめたものが表 1 である。

モデルは、先行研究 [2] のモデルを使用する。まず、N 個のノードと M 個のリンクを持つ静的・無向で重みのないネットワークを考える。各ノードは時間とともに変化する連続状態 xi ∈ R (0 ≤ i ≤ N ) を持つ。リンク (i, j) が適用される期間 0 ≤ t ≤ τ のダイナミク
スは、次式で表される。

dxi= xj − xi
dtdxj
= xi − xjdt(6)

i=1 j=1

karatedolphins

zebra

ノード

346227

リンク

78159111

平均次数4.588

5.1298.222

クラスター係数0.571

0.2590.876

直径584

密度0.1390.0840.316

リンク適用時間は τ = 0.1 から 5 まで 0.1 刻みで増加する値とし、各ノードの初期状態 xi (0) に 0 から 1までの乱数を与えて計算した結果が図 1 である。リン
クオーダーはランダムで、100 個のサンプルについて計算を行った。エラーバーは平均±標準誤差を表す。
図 1 を見ると、最終的な d の大きさは、zebra、karate、dolphins の順に小さくなっている。表 1 と比べると、クラスター係数と密度の値が大きいものほど、また直径の大きさが小さいほど d の値が小さくなっていることがわかる。

(4)

ここで、x(τ ) = (x1 (t) · · · xN (t))T 、I は N × N 単−2τ位行列、ε = 1−e2である。L(ij) はシングルリンクラプラシアン行列で、(L(ij) )ii = (L(ij) )jj = 1 と(L(ij) )ij = (L(ij) )ji = −1 で定義される。L(ij) の他の要素は 0 に等しい。したがって、リンク e1 , · · · , eM に対して、ネットワークの最終状態は以下のように決定される。
x(M τ ) = T x(0)
(5)

d100

10-110-210-1

ここで、T = (I −εL(eM ) )(I −εL(eM −1 ) ) · · · (I −εL(e1 ) )である。状態ベクトルは x(t) ≡ (x1 (t) · · · xN (t))T で表され、行列 T は初期状態ベクトル x(0) を最終状態ベクトル x(M τ ) に写像する。
次に、時刻 t = M τ のときの合意形成のレベルを定量化する距離 d を導入する。先行研究 [2] より、各ノードの初期状態 xi (0) (i ≤ i ≤ N ) が平均 0 と標準偏差σ を持つ独立かつ同一の正規分布に従うときの正規化

karatedolphins
zebra100τ101

図 1: 時間情報なしネットワークの d 値
次に、時間情報ありのネットワーク hypertext、contact、infectious について d の計算を行った。これらのネットワークは、会議等における対面コンタクトを表しており、ノードが人、リンクが一個人同士のコンタ

45クトである。一定時間ごとに記録したデータを使用しており、それぞれのリンクには接触があった時点の時刻情報が付加されている。したがって、仮に記録する時間間隔を a とすると、ある 1 組が 3a 時間連続で会話を行った場合、会話の回数は一回であるのにも関わらず、リンクはこの二人の間に 3 本繋がれるということになる。これらのネットワークの数値を表 2 に示す。

d100contact

ノード112274410

リンク208162824417298

平均次数39.196

15.50413.488

クラスター係数0.5400.6330.456直径349

密度0.353

0.057

0.033

100

10-1

10-1

100101τ

図 4: infectious の比較
また、hypertext、contact、infectious の d 値を比較したところ、ランダムリンクオーダーの場合と実際のリンクオーダーの場合どちらも hypertext、infectious、contact の順に d 値が小さいという結果が得られた。表2 を見ると、時間情報なしネットワークの場合と異なり、infectious より contact の方が密度とクラスター係数が大きく直径が小さいのにも関わらず、infectiousの方が contact よりも合意が取れているという結果になった。

(c) 一回の会話でリンクが複数本ある場合、重複を除去し最初の一本のみにして実際の時刻順にリンクを適用した場合。

d(a)
(b)

10-2
10-2(b) 実際の時刻順に変更した場合。

4100101τ(a) 時刻情報なしの時と同様にリンクオーダーがランダムな場合。

10-1100

図 3: contact の比較

以下のように d を計算するプログラムを 3 つ用意し、それぞれを hypertext について計算し比較を行った。
その結果が図 2 である。各ノードの初期状態 xi (0) に0 から 1 までの乱数を与え、100 個のサンプルについて計算を行った。

10010-2
10-410-610-810-1010-12(a)10-14(b)-1610(c)10-18-2
1010-1

infectious

dhypertext

10-1

10-210-2

表 2: 時間情報ありネットワークデータ
ネットワーク(a)(b)

まとめと今後の課題

本研究では、先行研究 [2] のモデルを使い時間情報ありとなしの複数のネットワークについて合意形成の速度の基準値を計算し比較を行った。時間情報なしの場合、密度とクラスター係数が大きく直径が小さいものほど合意がとれやすいことがわかった。また、リンクオーダーによって、合意形成の速度が加速または減速することを確認できた。今後は、長時間の会話が行われたリンクにはその分重みをつけるなどして、より現実に近づけて計算を行いたい。また、今回使用したモデルは一対一の会話のみを扱うものなので、3 人で行う会話のモデルも考えていきたい。

101τ

図 2: hypertext の d 値
図 2 を見ると、d は (a)、(b)、(c) の順に小さい値になっている。これより、リンクオーダーによって合意形成の速度に差が出ることが確認できた。実際のテンポラルネットワークでは、ランダムリンクオーダーのときよりもゆっくりと合意形成が行われることがわかる。また実際のリンクオーダーで、重複ありの場合と重複なしの場合を考えたが、τ を一定の値に取っているため、重複ありの場合の方がより現実に近いと考えられる。
contact と infectious に対してもランダムリンクオーダーの場合と実際のリンクオーダーの場合（重複あり）で比較したが、どちらについても hypertext と同様にリンクオーダーによって合意形成の速度に違いが見られ、ランダムリンクオーダーの方が合意が取れているという結果が得られた。（図 3,4）

参考文献
[1] 増田直紀, “テンポラルネットワーク — Temporal
Networks: A Short Introductory Survey”, 人工知能学会誌, 27 (4), 432–436 (2012).
[2] Naoki Masuda, “Accelerating coordination in
temporal networks by engineering the link order”, Scientific Reports 6, 22105 (2016).
[3] 増田直紀, 今野紀雄「複雑ネットワーク 基礎から応用まで」近代科学社 (2010).

46