1M4-2 信頼度つきギャップ分析による社会ネットワークからの高中心性 ノード群同定

信頼度つきギャップ分析による社会ネットワークからの

高中心性ノード群同定

Identifying High Centrality Nodes in Social Network based on Gap Analysis with Confidence Level

大原剛三

∗1 Kouzou Ohara

斉藤和巳

∗2 Kazumi Saito

木村昌弘

∗3 Masahiro Kimura

元田浩

∗4 Hiroshi Motoda ∗1

_{青山学院大学}

Aoyama Gakuin University

∗2

_{静岡県立大学}

University of Shizuoka ∗3

_龍谷大学

Ryukoku University ∗4

_大阪大学

Osaka University

This paper addresses a problem of identifying nodes having a high centrality value in a large social network based on its approximation derived only from nodes sampled from the network. We assume that a gap exists between two adjacent nodes ordered in descending order of approximations of true centrality values if it can divide the ordered list of nodes into two groups so that any node in one group has a higher centrality value than any one in another group with a given confidence level. Then, we incorporate confidence intervals of true centrality values and devise an efficient algorithm that applies a resampling-based framework to estimate the intervals as accurately as possible. Using a real world large social network, we empirically show that the gaps detected by the proposed method enable us to correctly identify a set of nodes having a high centrality value.

1.

はじめに

今日，FacebookやTwitterなどのソーシャルメディアの普及に より，インターネット上には巨大な社会ネットワークが構築され ている．ソーシャルメディアに一旦投稿された情報は，そのよう な社会ネットワークを通して急速，かつ広範囲に拡散され，我々 の日常における意思決定にも多大な影響を与えるため，近年， 社会学のみならず計算機科学も含めた多様な分野において社会 ネットワークの分析が進められている[Kleinberg 08, Chen 13]． そのような社会ネットワーク分析においては，幾つかの中 心性と呼ばれる指標が利用されている[Katz 53, Freeman 79,

Bonacichi 87, Brin 98, Zhuge 10]．中心性はネットワーク構造に 基づきノードを特徴づけるものであり，その値から各ノードが どのような意味で，どの程度重要かについての情報を我々にも たらしてくれる．また，ネットワークのスケールフリー性が次 数分布から導かれるように，ネットワーク全体の構造的特徴を 知る手がかりともなる．一方，近接中心性や媒介中心性などの ように，その値を求めるために対象ノードの隣接ノードの情 報のみならず，任意のノード間の最短経路などのようなネット ワーク全体にわたる情報を必要とするものがあり，それらに関 しては，ネットワークが大きくなるとその計算が困難になる． 実際には，そのような計算コストの高い中心性は，ノードペ アなどから導かれる値を基礎に，その平均値として定義され ることが多い．このことから，その計算コスト軽減に対する1 つのアプローチとしては，サンプリングによるノード数の削減 が考えられる．ノード数を制限することにより中心性の計算は 容易になるが，得られるのは近似値となるため，真の値との近 似誤差を精度良く推定することが重要となる．この問題に対し て，我々は近似誤差を精度よく推定するリサンプリング法に基 づいた枠組みを提案し，それにより得られる近似誤差（以下， リサンプリング誤差）が独立同分布の下でのサンプリングを仮 定した標準的な近似誤差（以下，標準誤差）よりも正確な誤差 範囲を与えることを実験的に示している[Ohara 14]． 一方，社会ネットワーク分析では，全ノードの中心性の値を 連 絡 先: 大 原 剛 三 ，青 山 学 院 大 学 理 工 学 部 情 報 テ ク ノ ロ ジー学科，〒 252-5258 相模原市中央区淵野辺 5-10-1， [email protected] 知ることよりも，高い中心性をもつノードが興味の対象となる ことが多い．そのため本稿では，高い中心性をもつノード集合 をサンプリングにより得られた中心性の近似値から精度よく同 定することを考える．具体的には，ノードを中心性の近似値の 降順に並べ，あるノード間で2つに分割したとき，上位集合 中の任意のノードが下位集合中のどのノードよりも大きい真 の中心性の値をもつ場合，それらのノード間にはギャップがあ るとし，そのようなギャップを中心性の近似値のみから一定の 精度で検出することを試みる．統計的な観点からは，これは， 与えられた信頼度の下で各ノードの中心性指標値の信頼区間 を求め，分割後の上位集合，下位集合間のその重複関係を調べ ることに相当する．そこで本研究では，その信頼区間の導出に 前述のリサンプリング誤差を導入し，実際の大規模社会ネット ワークを用いた評価実験を通して，標準誤差を利用するよりも 多くのギャップを検出し，かつ検出したギャップが高い中心性 をもつノード集合の同定に有用であることを示す．

2.

リサンプリング法に基づいた近似誤差推定

本節では，文献[Ohara 14]に従い，リサンプリング法に基 づいた近似誤差推定の一般的な枠組み，およびその近接中心性 と媒介中心性への適用について述べる．

2.1

一般的枠組み

いま，ある集合S（|S | = L）に対して，f をS中の各要素 に何らかの値を対応付ける関数とする．このとき，S に対す る fの平均値µ = (1/L)∑s∈S f (s)を，S の任意の部分集合T （_{|T| = N}）に対する f の値{ f (t)|t ∈ T, T ⊂ S }のみから推定す ることを考える．実際には，T に対するf の値から_µを直接 推定することはできないため，_µと_{µ(T) = (1/N)}∑_t∈T f (t)間 の近似誤差を，_µを仮定せずに推定する．そのために，任意の T ∈ T に対して，T _{⊂ S}，かつ_{|T| = N}であるようなS の部 分集合族_{T ⊂ 2}S _{を考える．このとき，µとµ(T)の近似誤差} RE(N)を以下のように定義する． RE(N)= √⟨(µ − µ(T))2⟩ T∈T = √ L− N (L− 1)N× √ 1 L ∑ s∈S ( f (s)− µ)2 ₍₁₎

1

The 29th Annual Conference of the Japanese Society for Artificial Intelligence, 2015

この式は，S からN個の要素をリサンプリングすることで得 られる_T に対して，T _{∈ T} に対する部分平均_µ(T)と真の平 均_µとの二乗平均平方根誤差（RMSE）を計算していると解 釈できる．ここで，右辺のうちNに依存するのは第1項のみ であり，第2項はNに依存しないこと，および，この第2項 が全体集合Sに対する関数 fの値の標準偏差となっているこ とから，第2項を定数項_σ，第1項をその係数項C(N)とし， RE(N)= C(N)σとする．このことから，実際には部分集合T をリサンプリングせず，定数L，σ，およびサンプリング数N が与えられた時点でRE(N)の値を計算可能なことがわかる．以 下では，このRE(N)をリサンプリング誤差と呼ぶ． 一方，より一般には，独立同分布の下でのサンプリングを前 提に，µとµ(T)の近似誤差の期待値を計算する．具体的には， t∈ Tがある確率分布p(t)に従って独立にSから選択されたと 仮定する．p(t)としては，p(t)= 1/Lのような経験的な一様分 布などが考えられる．このとき，_µと_µ(T)の近似誤差の期待 値は次式のように定義できる． S E(N)=√⟨(µ − µ(T))2⟩ = √ 1 N × √ 1 L ∑ s∈S ( f (s)− µ)2 ₍₂₎ この式も式(1)同様，右辺の第1項のみがNに依存し，第2項 は関数fの値の標準偏差となっていることから，実際にはTを サンプリングすることなく，その値を求めることができる∗1_． 以下，S E(N)を標準誤差と呼び，式(1)同様，右辺の第2項を 定数項_σ，第1項をその係数項D(N)とし，S E(N)= D(N)σ とする．ここで，C(N)≤ D(N)であり，C(L)= 0であるのに 対しD(L), 0であることに注意されたい．すなわち，あるN

に対してRE(N)≤ S E(N)であり，N_{= L}のときRE(N)は0と

なるが，S E(N)は0とはならない．

2.2

中心性指標への適用

次に，上記の近似誤差推定の枠組みを社会ネットワークにお けるノード中心性の推定問題に適用する．以下では，社会ネッ トワークを有向グラフG= (V, E)により表現する．ここで，V， およびE⊆ V × Vはそれぞれネットワーク中のノード集合と 有向リンク集合である． 2.2.1 近接中心性 まず，G中のノードu∈ Vに対して次式で定義される近接 中心性を考える． clsG(u)= 1 (|V| − 1) ∑ v∈V,v,u 1 splG(u, v) (3) ここで，splG(u, v)はグラフGにおけるノードuからノード vまでの最短経路長を表し，vがuから到達可能でなければ splG(u, v) = ∞とする．直観的には，ネットワーク中の他のど のノードにも比較的短い経路長で到達可能なノードほど近接中 心性は大きな値となる．この近接中心性を計算する一般的な方 法としては，基点ノードから1つのリンクを辿ることで新た に到達可能となるノード集合を漸進的に求めるburningアルゴ リズム[Newman 01]が知られているが，各ノードuに対する 近接中心性clsG(u)を求める計算量はO(|E|)であり，巨大な社 会ネットワークに対しては膨大な計算時間を要する． この近接中心性に対して，前述のリサンプリングに基づいた 近似誤差推定の枠組みを適用することを考える．ここでは，対象 ∗1 RE(N)，S E(N) いずれの計算においても σ が必要となるが，|S | = L が大きい場合はそもそも_{σ の計算が困難であるため，実際にはその} 近似値として，_|S′_{| = L}′が十分小さい部分集合 S′⊂ S から現実的 な計算時間で得られる標準偏差_σ′を近似値として用いる． ノードuを除くVからサンプリングしたノード集合T（|T| = N） のみから求められるuの近接中心性の近似値clsG(u; T )と真の 値clsG(u)の近似誤差を考えることになる．そのために，前節 における全サンプル集合S，評価関数 f を近接中心性の計算 に合わせて具体化する．まず，近接中心性はノード集合全体 に対する値ではなく，各ノードに対する値であるため，Sに関 しては，対象ノードをuとしたとき，Su= V \ {u}とする．こ こで，_\は集合差を意味する．一方，clsG(u)はその定義より， ノードu以外のノードvに対して求められる1/splG(u, v)の平 均値であるため，評価関数fに関しては，fu(v)= 1/splG(u, v) とする．これにより，clsG(u; T )を(1/N) ∑ v∈T fu(v)として求め ることができ，式(1)，および(2)に従い，RE(N)，S E(N)を それぞれ計算することが可能となる． 2.2.2 媒介中心性 次に，次式で定義されるノードuの媒介中心性について考 える． btwG(u)= 1 (|V| − 1)(|V| − 2) ∑ v∈V,v,u     ∑ w∈V,w,u w,v nspG(v, w; u) nspG(v, w)     (4) ここで，nspG(v, w)はグラフGにおけるノードvからwまでの 最短経路数，nspG(v, w; u)はそのうちノードuを経由する最短 経路数を表す．直観的には，ノードuを経由する2ノード間の 最短経路数が多いほど，uの媒介中心性btwG(u)の値は大きく なる．この媒介中心性を求める標準的な方法としては，Brandes のアルゴリズム[Brandes 01]が知られており，各ノードuに対 してbtwG(u)を求める計算量は近接中心性同様O(|E|)である． いま，ノードuの真の媒介中心性の値btwG(u)と，uを除くV の部分集合T（|T| = N）から求められるその近似値btwG(u; T ) の近似誤差を2.1節の枠組みに基づき推定することを考える． 全サンプル集合Sに関しては，媒介中心性も全ノード集合では なく個々のノードに対して定まる値であるため，近接中心性と 同様に対象ノードuに対してSu= V \{u}とする．一方，式( 4) 中のカッコ内の項を関数btwG(u; v)とすると，btwG(u)はノー ドu以外のノードvに対して求められるbtwG(u; v)/(|V| − 2)の 平均と考えられる．したがって，fu(v)= btwG(u; v)/(|V| − 2)と することで，任意の部分集合Tに対するノードuの媒介中心性 btwG(u; T )を(1/N) ∑ v∈T fu(v)として求めることができ，式(1)， (2)に従いRE(N)，S E(N)をそれぞれ計算することができる．

3.

信頼度つきギャップ検出法

本節では，ネットワーク中のノードの部分集合から推定され る中心性の近似値のみを用いて，与えられた信頼度の下で実際 に高い中心性をもつノード集合を同定する手法を考える．まず， ここでの問題を形式的に定義する．ネットワークG(V, E)に対 して，µG(v)をノードv∈ Vの真の中心性指標値とし，µG(v; T ) をノードの部分集合T⊆ Vから得られるその近似値，σ(v; |T|) をRE(v;|T|)やS E(v;|T|)のような近似誤差とする．また，ノー ドvが与えられたとき，µG(v; T )に基づくノード集合V の互 いに疎な分割VH(v; T )= {u ∈ V; µG(u; T )≥ µG(v; T )}，および VL(v; T )= {w ∈ V; µG(w; T )< µG(v; T )}を考える．このとき，統 計における信頼区間推定の考えの下，ここでの問題は，任意 のu∈ VH(v; T )とw∈ VL(v; T )が以下の不等式を満たすような ノードv∈ Vをすべて見つける問題と定義できる． µG(u; T )− z(α) · σ(u; |T|) > µG(w; T )+ z(α) · σ(w; |T|) (5)

2

ここで，0< α < 1であり，z(α)は標準正規分布における信頼度 C= 100(1−α)%に対する上側信頼限界値である．言い換えるな ら，この不等式を満たす場合，信頼度Cで任意のu∈ VH(v; T ) とw∈ VL(v; T )に対してµG(u)> µG(w)が成り立つ．ここで， 上位集合VH(v; T )が我々が同定したいノード集合であり，以 下，ノードvとv′∈ arg max_{w∈VL(v;T )}µG(w; T )間にはギャップが 存在するという．この問題をナイーブに解く場合，各ノードv に対して|VH(v; T )||VL(v; T )|個のノードペアについて上記の不 等式を満たすかどうかを調べる必要があるため，その計算量は O(|V|3_{)となり，ネットワークが大規模化した場合はその計算} は困難となる． これに対して，V_H(v; T ) の誤差下限 minu∈VH(v)(µG(u; T ) − z(α)σ(u; |T|))，およびVL(v; T )の誤差上限maxw∈VL(v)(µG(w; T )+ z(α)σ(w; |T|))をそれぞれLB(VH(v); T, α)とU B(VL(v); T, α)した とき，ここでの問題は，与えられた_αに対してLB(VH(v); T, α) > U B(VL(v); T, α)を満たすすべてのv ∈ Vを見つける問題と考 えられる．LB(VH(v); T, α)とU B(VL(v); T, α)は，ノード集合V を一度走査するだけで任意のv∈ Vに対して同時に計算可能 であるため，全体の計算量はO(|V|2_{)となる．しかし，ネット} ワークが大きくなった場合，そのようなノードをすべて見つけ ることはまだ難しい． そこで，本研究では，中心性指標の近似値µG(v; T )の降順 に並べたノードリスト(v1, v2, · · · , v|V|)を考える．すなわち， 任意のi ∈ {1, · · · , |V| − 1}に対して，µG(vi; T ) ≥ µG(vi+1; T ) を仮定する．このとき，LB(VH(vk); T, α)はLB(VH(vk); T, α) = min(LB(VH(vk−1); T, α), µG(vk; T ) − z(α)σ(vk;|T|)) と い う よ う に 再 帰 的 に 定 義 可 能 で あ り，同 様 に ，U B(V_L(vk); T, α) も U B(VL(vk); T, α) = max(UB(VL(vk+1); T, α), µG(vk+1; T ) + z(α)σ(vk+1;|T|))と定義できる．この定義に従えば，すべての v∈ Vに対するLB(VH(v); T, α)とU B(VL(v); T, α)をノードリス ト(v1, v2, · · · , v|V|)をそれぞれに対して一度走査するだけで求め ることが可能となる．これは，ノードリストを二度走査するだけ ですべてのギャップを同定可能であることを意味する．具体的に は，最初の走査（forwardステップ）において，kを1から|V|−1 まで変化させつつLB(VH(vk); T, α)を求め，続く二度目の走査 （backwardステップ）において，kを|V|から2まで変化させつつ U B(VL(vk); T, α)を計算し，LB(VH(vk); T, α) > UB(VL(vk); T, α) が成り立つ場合にギャップを同定する．この手法における計算 量に関しては，ノード集合のソーティングにかかる計算量が支 配的となるため，O(|V| log |V|)と考えることができ，大規模な 社会ネットワークに対しても現実的な時間でのギャップ分析が 可能といえる．以下に，同定したギャップの集合をAとしたと きの提案法の手続きをまとめる． 1. （初期化） A ← ∅，LB(VH(v1); T, α) = µG(v1; T )− z(α)σ(v1;|T|))， U B(VL(v|V|); T, α) = 0とする． 2. （Forward step） kを2から|V| − 1まで変化させ，LB(VH(vk); T, α)を再帰 的に計算． 3. （Backward step） kを_{|V| − 1}から2まで変化させ，以下を実行． ・U B(VL(vk); T, α)を再帰的に計算． ・A← A ∪ {vk} if LB(VH(vk); T, α) > UB(VL(vk); T, α) 4. 解集合Aを出力して終了． 以 下 で は ，式 (5) に お い て ，近 似 誤 差 σ(v; |T|) と し て σ(v; |T|) = 0，σ(v; |T|) = S E(v; |T|)，σ(v; |T|) = RE(v; |T|)を 用いた3つの手法を考え，それぞれナイーブ法，S E法，RE 法と呼ぶ．ナイーブ法は常に_µG(v; T )= µG(v)を仮定するため， µG(vk; T ), µG(vk+1; T )であるようなすべてのkに対して，ノー ドvkとvk+1の間にはギャップが存在すると同定する．一方， RE(v;|T|)と比較して，S E(v;_|T|)は_µG(v; T )の近似誤差を過大 評価するため，S E法により同定されるギャップ数はRE法に 比べて少なくなる．次節では，これらの手法を実世界の社会 ネットワークを用いて実験的に評価する．

4.

評価実験

前節で提案したギャップ検出法を，実際の大規模ネットワー クを用いて実験的に評価した．本実験で用いたネットワーク は，Twitter∗2から抽出したフォロワーネットワークである．具 体的には，2011年3月5日から3月24日までの約3週間に わたって収集した201,297,161ツイートの投稿者から，この期 間中に200件以上のツイートをした1,088,040名の投稿者を抽 出し，その投稿者間のフォロー関係をネットワーク化した有 向グラフを作成した．そのノード数は1,088,040，リンク数は 157,371,628である． 本実験では，このネットワーク中のノードのうち，すべて のノードから求めた真の中心性の値において上位100ノード を対象にナイーブ法，S E法，RE法の各手法を評価した．実 験手順としては，ノード集合Vからノードを1つずつランダ ム非復元抽出し，それを順次部分集合T に加え，ノード被覆 率_|T|/|V|が0.01増加するごとに各手法の検出したギャップ数 （検出数），およびその中で不正解であったギャップ数（不正解 数）を調べた．実験では，これをR= 1, 000回試行し，信頼度 95%（α = 0.05）の下での各被覆率ごとのギャップ検出数，不 正解数の平均を求めた． 図1に近接中心性に対する結果を示す．グラフの横軸（ cov-erage）は被覆率であり，縦軸（gaps）は各試行でのナイーブ法 のギャップ検出数が100となるように各手法の検出数，不正解 数を正規化した値の1,000回試行における平均値である．その ため，グラフ中のナイーブ法の検出数は常に100となってい る．ここで，被覆率c，r回目の試行において，各手法が検出し たギャップ集合をA(c, r)，その中で正しく検出されたギャップ 集合をA∗(c, r)，ナイーブ法が検出したギャップ集合をAnv(c, r) としたとき，グラフ中の実線（Detected gaps）で表される検出 数，および破線（Incorrect gaps）で表される不正解数はそれぞ れ次式で定義される． (検出数) 1 R R ∑ r=1 |A(c, r)| |Anv(c, r)| × 100 (6) (不正解数) 1 R R ∑ r=1 |A(c, r) \ A∗_{(c, r)|} |Anv(c, r)| × 100 (7) 各手法を比較すると，ナイーブ法の検出数はいずれの被覆 率でも高いものの，不正解数も多い．被覆率が高くなるにつ れて不正解数は減少するが，S E法，RE法と比較してその値 は非常に大きい．一方，S E法とRE法に関しては，被覆率が 0.2あたりまではほぼ同程度の検出数であり，ナイーブ法と比 べると少ないが，S E法の検出数がその後も大きな伸びを示さ ないのに対し，RE法の検出数は徐々にS E法の検出数を上回 り，被覆率が0.9を超えるあたりからその数は急増し，最終的 には100となっている．これは，RE法が用いるリサンプリン グ誤差が誤差範囲をより厳密に評価するのに対し，S E法が用 いる標準誤差は誤差範囲を過大評価する傾向にあるためであ ∗2 https://twitter.com

3

0 0.2 0.4 0.6 0.8 1 0 20 40 60 80 100 coverage gaps Detected gaps Incorrect gaps (a) ナイーブ法 0 0.2 0.4 0.6 0.8 1 0 20 40 60 80 100 coverage gaps Detected gaps Incorrect gaps (b) SE 法 0 0.2 0.4 0.6 0.8 1 0 20 40 60 80 100 coverage gaps Detected gaps Incorrect gaps (c) RE 法 図1:近接中心性に対する実験結果 0 0.2 0.4 0.6 0.8 1 0 20 40 60 80 100 coverage gaps Detected gaps Incorrect gaps (a) ナイーブ法 0 0.2 0.4 0.6 0.8 1 0 20 40 60 80 100 coverage gaps Detected gaps Incorrect gaps (b) SE 法 0 0.2 0.4 0.6 0.8 1 0 20 40 60 80 100 coverage gaps Detected gaps Incorrect gaps (c) RE 法 図2:媒介中心性に対する実験結果 る．そのため，被覆率が高くなり，中心性の近似値が真の値に 近くなっても，S E法における上位集合の誤差下限と下位集合 の誤差上限は多くの場合重複してしまい，ギャップの検出が困 難となっている．これに対してRE法が用いるリサンプリング 誤差は誤差範囲を厳密に評価するものの過小評価はしないた め，被覆率が高くなるにつれて検出数が多くなる一方，不正 解数はほとんど増えず，ほぼ0という結果になっている．よ り安全な誤差範囲を想定するS E 法でも，不正解数に関して は同様の傾向となっている．不正解数が少ないことは，検出し たギャップにより高中心性ノード集合が精度よく同定できるこ とを意味する．なお，同じ被覆率では，常にRE法の検出数は S E法の検出数以上となっている．図2からは，これらの傾向 が媒介中心性に対する結果にも共通していることがわかる．

5.

おわりに

本稿では，社会ネットワークにおけるノード中心性に関し て，サンプリングした一部のノード集合から求められるその 近似値のみを用いて，真の中心性の値が高いノード集合を効 率的に，かつ高精度で同定する手法を提案した．提案法では， 真の中心性の値とその近似値の近似誤差としてリサンプリン グ誤差を用いることで，与えられた信頼度の下での真の中心性 の値の信頼区間を高精度で推定し，中心性の近似値で順序づけ られたノード集合を2回走査するだけでノード間のすべての ギャップを検出する．実世界の大規模社会ネットワークを用い た評価実験では，信頼度95%の下，提案法が標準誤差を用い る手法より多くのギャップを検出し，かつ検出したギャップに より高中心性ノード集合を精度よく同定できることを示した． 今後の課題としては，他のサンプリングに基づくアプローチと の比較が挙げられる．

謝辞

本研究で用いたデータは東京大学 鳥海不二夫氏，和歌山大 学 風間一洋氏によるものである．また，本研究は科学研究費 補助金基盤研究(C) (No. 26330261)の補助を受けた．

参考文献

[Bonacichi 87] Bonacichi, P.: Power and centrality: A family of measures, Amer. J. Sociol., Vol. 92, pp. 1170–1182 (1987) [Brandes 01] Brandes, U.: A faster algorithm for betweenness

centrality, Journal of Mathematical Sociology, Vol. 25, pp. 163–177 (2001)

[Brin 98] Brin, S. and L.Page, : The anatomy of a large-scale hy-pertextual web search engine, Computer Networks and ISDN

Systems, Vol. 30, pp. 107–117 (1998)

[Chen 13] Chen, W., Lakshmanan, L., and Castillo, C.: Informa-tion and influence propagaInforma-tion in social networks, Synthesis

Lectures on Data Management, Vol. 5(4), pp. 1–177 (2013)

[Freeman 79] Freeman, L.: Centrality in social networks: Con-ceptual clarification, Social Networks, Vol. 1, pp. 215–239 (1979)

[Katz 53] Katz, L.: A new status index derived from sociometric analysis, Sociometry, Vol. 18, pp. 39–43 (1953)

[Kleinberg 08] Kleinberg, J.: The convergence of social and technological networks, Communications of ACM, Vol. 51, No. 11, pp. 66–72 (2008)

[Newman 01] Newman, M. E. J.: Scientific collaboration net-works. II. Shortest paths, weighted networks, and centrality,

Physical Review E, Vol. 64, p. 016132 (2001)

[Ohara 14] Ohara, K., Saito, K., Kimura, M., and Motoda, H.: Resampling-based Framework for Estimating Node Central-ity of Large Social Network, in Proc. of DS 2014, pp. 228– 239(2014)

[Zhuge 10] Zhuge, H. and Zhang, J.: Topological centrality and its e-Science applications, Journal of the American Society

of Information Science and Technology, Vol. 61, pp. 1824–

1841 (2010)

4