一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

コリンク構造に着目した多重グラフの特性分析

Characteristics Analysis of Multi
Multi Graphs
Focused on CoCo-link Structure
Structure

小出 明弘♥
風間 一洋♣

斉藤 和巳♦
鳥海 不二夫♠

Akihiro KOIDE Kazumi SAITO
Kazuhiro KAZAMA Fujio TORIUMI

従来ソーシャルネットワークにおけるユーザ間のメッセージのやりとりは，人間関係の有無とととらえ，単純グラフとみなして分析
やりとりは，人間関係の有無
されることが多かった．一方で，メッセージ数を考慮することで，多重グラフとみなすこともできる．本論文では，多重グラフとみなすこともできる．本論文では，ネットワーク内で
本論文では，ネットワーク内で中心的な役割を果たしていると考えられる高次数ノードの中心的な役割を果たしていると考えられる 高次数ノードの相互高次数ノードの 相互関係に着目し，多重グラフ関係に着目し，多重グラフとみなした場合に着目し，多重グラフ とみなした場合と単純グラフとみなした場合と単純グラフとみなしと単純グラフとみなした場合でのた場合で の違いを違いを分析した．
分析した．我々はコリンク率をベースとした従来の分析手法を多重グラフに適用できるように
来の分析手法を多重グラフに 適用できるように拡張適用できるように 拡張した
拡張した手法をした手法を提案した
提案 した．
した． さらに，Twitter
さらに，TwitterのフォローネットワークとTwitterのフォローネットワークとMentionのフォローネットワークとMentionネ
Mentionネットワークの高次数ユーザをットワークの高次数ユーザを対象に分析の高次数ユーザを対象に分析した．その結果，対象に分析した．その結果，単純グした．その結果，単純グ
ラフでは，多くのユーザから言及される，または多くのユーザに発言しても双方向コミュニケーションは成立してい発言しても双方向コミュニケーションは成立していないユーザしていないユーザしか抽出されないのに対して，多重グラフでは，か抽出されないのに対して， 多重グラフでは，メッセージのやり多重グラフでは， メッセージのやり取りの繰り返し取りの繰り返しによの繰り返しにより形成されるにより形成される，り形成される，高頻度コミュニケーションユー
ザを検出できることがザを検出できることが示された．
された．
Message passing between users over socialsocial networks wereanalyzed
analyzed as simple graphs conventionally.
conventionally. On the other
hand, it is ppossibleossible to regard such networks
networks as multigraphs which focus on the number of messages between
users.
users. In this paper, by focus
focusing
cusing on the interaction of highdegree nodes who are considered as main rule players,
players, weanalyzed the differences
differences between the results regarded as
multimulti-graphs and those as simple graphs. To this end, we
propose to extend our previous analysi
analysis method based on
the coco-link to a method for multi graphs. In our analyses
using high degree nodes on Twitter’mentionentionTwitter ’s follow and m
networks
networks. As a result, we show that quite frequent mutualcommunication users can be obtained in multi graphs,
while one directional communication users are likely to behigh degree nodes in simple graphs.
graphs.

♥学生会員 静岡県立大学大学院経営情報イノベーション
研究科修士課程 j11103@u-shizuoka-ken.ac.jp♦
正会員 静岡県立大学経営情報学部
k-saito@u-shizuoka-ken.ac.jp♣
正会員 日本電信電話株式会社未来ねっと研究所
kazama@ingrid.org♠
非会員 東京大学大学院工学研究科
tori@sys.t.u-tokyo.ac.jp

1. はじめに
近年ミニブログと呼ばれる，ブログとSNSを組み合わせたサービスが増加している．その中で，短文投稿サービスであるTwitter1は急激にユーザ数を伸ばしており，ユーザ行動をリアルタイムに観測できることから，研究対象として注目され，様々な知見が得られてきた[1]．
Twitterの特徴として，フォローの仕組みがあげられる．
Facebook2やmixi3などの代表的なSNSでは，相手の承認がな
ければ情報を閲覧できないが，Twitterでは，自分の興味のある話題を提供するユーザをフォローするだけで，そのユー
ザのTweetを継続的に閲覧できるようになる．これにより，情報が伝播するフォローネットワークが形成される．これは有向で単純グラフである．
また，Twitterの代表的な機能として，Mention Tweetがある．Mention Tweetは，Tweetに@User名を含んだものであり，@User名で指定されたユーザはそのTweetを自分宛のTweetとして確認できる．このような場合には， Mention
Tweetを行ったユーザと@User名で指定されたユーザの間にメッセージのやり取りという形でコミュニケーションが行われたと考えられる．そこで，Mentionしたユーザ同士にリンクを張ることによって，Mentionネットワークを表現できる[2]．このネットワークは，フォローネットワークと同様に，人間関係の有無をリンクとして考えれば，有向で単純なグラフとなる．一方，ユーザ間のメッセージは複数回やり取りされることもあるので，ノード間に複数のリンクを有した多重グラフとしても表現できる．
このような人間関係ネットワークを対象にした，ネットワ
ークの成長や情報拡散現象のモデル化の研究は代表的なタスクであり，将来予測やバイラルマーケティングの分野への応用が期待されている．従来のネットワークの生成モデルとして，「次数の高いノードほど繋がりやすい」という仮定に基づくBAモデル[3]や，「友人の友人は，友人になりやすい」という仮定に基づくCNNモデル[4]などがあげられる．また，情報拡散現象はIC（Independent Cascade）モデルやLT（Liner Threshold）モデルなどの確率的なアプローチによりモデル化されている[5]．
その際，ネットワーク全体の特徴量だけでなく，個々のノードの特徴を考慮することで，ネットワークの成長や情報拡散現象をより正確にモデル化できると考えられる．また，
Mentionネットワークのような多重グラフを分析できれば，ユーザの関係の強弱を考慮した，より緻密なモデルの構築が可能であると考えられる．
本研究では，ソーシャルネットワークにおいて特に重要な役割を果たしていると考えられる高頻度コミュニケーショ
ンユーザに着目して，ネットワークの成長や情報拡散を表現するモデルを構築する．その第一歩として，本論文では高次数ノードを対象に単純グラフで分析した場合と多重グラフで分析した場合に，分析結果にどのような違いがみられるかを明らかにする．具体的には，単純グラフであるフォローネ
ットワークと多重グラフであるMentionネットワーク，さらに後者を単純化した3つのネットワークの基本統計量を分析する．次に，単純グラフのコリンク構造を解析する手法[6]1http://twitter.com

2http://www.facebook.com/
3 http://mixi.jp/

1― 13 ―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

図 1 フォローNW
フォローNW の出次数分布

図 3 単純・多重 Mention NW の出次数分布

Fig.1 InIn-degree Distribution of Follow Network

Fig.3 Simple and Multi graph InIn-degree Distribution of
Mention Network

図 2 フォローNW
フォローNW の入次数分布
図 4 単純・多重 Mention NW の入次数分布

Fig.2 OutOut-degree Distribution of Follow Networkを，多重グラフに拡張した手法を提案する．さらに，実際にMentionネットワークを2種類の手法で分析して，単純グラフ化の問題点と，多重グラフとしての分析によって発見可能な特徴について述べる．

2. 使用データと基本統計量分析
本章では，本分析で利用するフォローネットワークとMention ネットワークについての概要と，各ネットワークの基本統計量について述べる．

2.1 使用データ

1 つ目は，日本語で書かれた Tweet を公開しているユーザのフォローネットワークである．2011 年 1 月 31 日時点において累積 200 回以上 Tweet しているユーザをノードとして，
フォローユーザから被フォローユーザへ有向リンクを張る
ことにより有向ネットワークを作成した．ネットワークのノード数は 1,088,040，リンク数は 157,371,628 である．
2 つ目は，Twitter 上でのコミュニケーションによって構築される Mention ネットワークである．2011 年 3 月 7 日から 3 月 23 日までに投稿された@User を含む Tweet から，各ユーザをノードとし，@User で指定されたユーザにリンクを張ることで有向ネットワークを生成した．ネットワークのノ

Fig.4 Simple and Multigraph OutOut-degree Distributionof Mention Network
ード数は 4,565,085，リンク数は単純グラフ化 Mention ネッ
ト ワーク （以 下単純 Mention ネッ トワ ーク） の場合で58,514,337，多重グラフ化 Mention ネットワーク（以下多重 Mention ネットワーク）の場合で 174,794,583 である．

2.2 各ネットワークの基本統計量
ネットワークの基本統計量

表1に，各ネットワークの基本統計量を示す．フォローネ
ットワークとMentionネットワークを比較すると，フォロー
ネットワークは平均次数が高く密なネットワークである．また，入次数と出次数に強い正の相関がある．これに対して，
単純・多重Mentionネットワーク共に平均次数は小さく，疎なネットワークである．また，入出次数相関もそれほど高くない．Mentionネットワーク同士を比較すると，多重Mention
ネットワークでは，最大入次数が単純Mentionネットワークに比べて非常に大きくなっている．一方，最大出次数に関しては，それほど大きくはない．
続いて，各ネットワークの出次数・入次数分布を図1～4 にそれぞれ示す．横軸に次数，縦軸にその次数を有するノード数をプロットした．フォローネットワークで左端が平坦にな

2― 14 ―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

表 1 各種ネットワークの基本統計量
Table 1 Basic Statistics of each Network
Mention NW
単純
多重

フォロー
NW
平均次数

144.6

11.2

38.3

最大入次数

175,616

133,326

423,606

最大出次数

97,938

7,022

11,094

入出次数相関

0.735

0.159

0.259

っている理由は，対象を累計ツイート数200以上のユーザに絞っているからである．
このグラフより，フォローネットワーク，単純・多重
Mentionネットワーク共にスケールフリー性を有することが確認される．また，次数分布は，フォローネットワークでは，入次数・出次数でそれほど変化しないが，Mentionネッ
トワークでは，入次数と出次数で大きく異なる．
さらに，図5 に多重Mentionネットワークのノード間の多重リンク数の分布を示す．リンク数はスケールフリー性を有した分布となっており，62.8%のリンク数は1であるが，最大で3,092本のリンクが張られている．このことから，無向グラフ化や単純グラフ化により，多重Mentionネットワークに存在するはずの重要な特徴が失われる可能性がある．

3. コリンク率
本章では，本分析で用いる評価手法について述べる．ここで ， ネ ッ ト ワ ー ク を  = (, ) と 定 義 し ， ノ ー ド 集 合 を
 = { ,  , … ,  }，リンク集合を × の部分集合とする．
なお，は全ノード数を表す．各ノード ∈ に対し， からのリンクを有するノード集合（子ノード集合）を( ) = ;  ∈ とし， へのリンクを有するノード集合（親ノード集合）を( ) =  ;  ∈ とする．この時，ネットワー
ク全体のコリンク率は以下のように定義されている[7]．
() =||∑ ∈|( ) ∩ ( )|.

図 5 Mention NW の各ノード間の多重リンク数
Fig.5
Fig.5 Number of Multiple Links of Mention NW
なお|( )|，|( )|が0になるとき，本数式は定義されない．式（2）と（3）の調和平均を取ることにより，平均コリンク率として以下の評価式を得る．
×|( )∩( )|=.
(4)
( ) = 

式（4）は，各ノードの入リンク, 出リンクが全てコリンクとなっている時1となり，コリンクがない時0となる.

3.2 多重グラフのノードの多重グラフのノードのコリンク率
ドのコリンク率

本節では先述の平均コリンク率を多重グラフにも適用できるように拡張する．
各リンク ∈ に対し，リンクの本数を とすると，各ノード間のリンクの本数を × の行列として以下のように表現できる．なお，ノード と の間にリンク が存在しない時， = 0とする．

= ⋮


(1)

コリンク率とは，次数に対する相互結合の割合を示す指標である．本稿では，ネットワーク内の高次数ノードに対してコリンク率を算出できるように，ネットワーク全体ではなく個々のノードに対してコリンク率を定義する．3.1 節では，単純グラフの場合のノードのコリンク率を定義し，3.2 節では，3.1 節のノードのコリンク率を多重グラフに拡張したノードのコリンク率を定義する．

( ) =( ) =|( )∩( )||( )|. （2）|( )∩( )||( )|

. （3）

⋯ 
⋱
⋮  ,  ∈ ℕ⋯ 

この時，任意のノード のコリンク率( )，( )を以下のように定義する．
( ) =3.1 単純グラフのノードのコリンク率
単純グラフのノードのコリンク率

本節では，単純グラフ上での各ノードを対象にしたコリン
ク率を導出する．ノード に対し，入次数に対する双方向リ
ンク数より得られるコリンク率( )，出次数に対する双方
向リンク数より得られるコリンク率( )をそれぞれ以下のように定義する．

|( )||( )|( ) ( )( ) =∑ ∈ ∩  ( , )








. （5）

∑ ∈  . （6）∑ ∈  ∑ ∈ ∩  (,)










ここで，任意のノード ， において，リンク ， が存在すると仮定すると，式（5），式（6）では ， の最小値を選択する．友人間のメッセージのやりとりを考慮すると，一方的なメッセージの送信では両者の間にコミュニケーシ
ョンが成り立ったとは言えず，互いにメッセージのやり取りがなされることで，初めてノード間で密なコミュニケーションが行われたと考えられる．このことから，式（5），式（6）は式（2），式（3）の自然な拡張である．前節と同様に，平
均コリンク率を式(5)と式(6)の調和平均をとって，次のように定義する．

3― 15 ―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文
( ) =DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012





( ) ( )=×∑ ∈ ∩  ( ,)∑ ∈   ∑ ∈  








.（7）

式（5），式（6）は全てのノードと相互リンクしていることに加え，リンク数が一致しているとき，最大値を示す．しかし，全てのノードと相互リンクしていても，両方のリンク数に大きな差がある場合には，平均コリンク率はそれほど大きくならない．式（7）は，コリンク率( )，( )がともに高くなる時高い値を示す．

4. 評価
本章では，現実の多重リンクを有したネットワークを用いて，単純グラフとのネットワーク構造の差異を分析する．

4.1 評価実験の詳細

本分析では，ネットワーク内で中心的な役割を果たすと考えられる高入次数ノード，高出次数ノードに着目する．フォ
ローネットワークと単純 Mention ネットワークの場合は，
高入次数ノード，高出次数ノードとして，それぞれ |( )|，|( )|が大きいノードを順次選定する．また，多重 Mention
ネットワークの場合は，高入次数ノード，高出次数ノードとして，それぞれ∑ ∈( )  , ∑ ∈( )  が大きいノードを順次選定する．本分析では，ネットワークごとに上位 1000
ノードを選定し，分析の対象とした．

図 6 フォローNW
フォローNW の入次数上位の入次数上位 1000 ノードの平均コリンク率
Fig.6 Average CoCo-link Ratio of Top 1000 InIn-degree Usersof Follow Network

4.2 実験結果

フォローネットワークの入次数の上位 1000ノードの平均
コリンク率と出次数上位1000ノードの平均コリンク率の次数による順位に伴う変化を図6，図7に示す[6]．横軸はノードを次数順に並べた時の順位を，縦軸は各ノードの平均コリンク率を表す．また，平均コリンク率が高くなるにはノードの入次数と出次数の差が小さいことが必要条件であるため，今後の共通の設定として，高入次数ノードをプロットする際には入次数に対する出次数比を，高出次数ノードをプロットする際には出次数に対する入次数比を閾値で分割し，異なるマーカを用いる．本分析では，閾値を0.5とした．
図 6 では，高コリンクノードと低コリンクノードの 2 つのタイプに大別されるが，図 7 では大部分は高コリンクノードで構成されており，
図 6 のような二種類の構造は見られない．
続いて，単純 Mention ネットワークの次数上位 1000 ノードの分析結果を図 8 と図 9 に示す．図 8 では，ほとんどのノードの平均コリンク率が 0.1 以下であり，図 6 のフォローネ
ットワークの結果とは大きく異なる．図 9 では，ほとんどのノードの平均コリンク率が 0.1 以下であるが，図 8 とは異なりやや平均コリンク率の高いノードが現れる．しかし，図 7と比較すると，ほとんどのノードが低コリンクノードである．
したがって，
単純 Mention ネットワークの高次数ユーザは，入次数・出次数ともに低コリンクの傾向が強いノードが検出され，フォローネットワークの構造と異なる特徴を持つ．
最後に，多重 Mention ネットワークの次数上位 1000 ノードの分析結果を図 10，図 11 に示す．特にランキング上位のノードは，図 8 の分析結果とほとんど変わらないが，ランキ
ングが下位になるにしたがって，平均コリンク率の高いノードが現れる．図 11 では，各ノードの平均コリンク率が低コ
リンクから高コリンクまで分散している．図 9 では，平均コリンク率はそれほど大きくはならないが，多重 Mention ネットワークではフォローネットワークで見られるような高コリンクノードが得られている．

図 7 フォローNW
フォローNW の出次数上位の出次数上位 1000 ノードの平均コリンク率
Fig.7 Average CoCo-link Ratio of Top 1000 OutOut-degree Usersof Follow Network

5. 考察

単純 Mention ネットワークと多重 Mention ネットワークの分析結果に大きな差が見られた理由を考察する．まず，2つのネットワークの次数上位 1000 ノード集合の類似性を，Jaccard 係数を利用して調査する．Jaccard 係数は，2 つの集合間の類似度を測る指標であり，ネットワークの次数上位1000 ノード集合を = { , … ,  }， = { , … ,  }とすると，以下のように定義される．
J(, ) =

|∩|
|∪|

．（8）

単純 Mention ネットワークと多重 Mention ネットワークの入次数上位 1000 ノード集合の Jaccard 係数は 0.638，出
次数上位 1000 ノード集合の Jaccard 係数は 0.131 であり，多重 Mention ネットワークでは，特に出次数の場合で，単純グラフと多重グラフとでは高次数ノード集合が大きく異4― 16 ―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

図 8 単純 Mention NW の入次数上位の入次数上位 1000 ノードの平均コリンク率
平均コリンク率

図 10 多重 Mention NW の入次数上位の入次数上位 1000 ノードの平均コリンク率

Fig.8
Fig.8 Average CoCo-link Ratio of Top 1000 InIn-degree Usersof Mention Network over Single Graph

Fig.10 Average CoCo-link Ratio of Top 1000 InIn-degree Usersof Mention Network over Multiple Graph

図 9 単純 Mention NW の出次数上位の出次数上位 1000 ノードの平均コリンク率
平均コリンク率

図 11 多重 Mention NW の出次数上位の出次数上位 1000 ノードの平均コリンク率

Fig.9
Fig.9 Average CoCo-link Ratio of Top 1000 OutOut-degree Usersof Mention Network over Single Graph

Fig.11 Average CoCo-link Ratio of Top 1000 OutOut-degree
Users of Mention Network over Multiple Graph

なる．このことから，少数のユーザに対して複数の Mentionを行うユーザが高出次数ユーザとして現れ，結果が大きく異なったと考えられる．
また，ユーザがMentionする理由として，「返信」と「引用」の2種類があることも一つの要因であると考えられる．
返信は，特に親しいユーザ間で繰り返される場合と，著名人
ユーザに一方的に行う場合があり，TwitterではReply 機能を利用する．引用は，フォロワーに有用なTweetや，多くのユーザに伝えたい情報を拡散させる際に行われ，TwitterではRetweet機能を利用する．これらの利用形態から， 返信は特定少数のユーザ間で繰り返しやり取りされる傾向があると考えられる．一方，引用は多くのユーザが並行して行うが，そのやり取りは大抵一過性であると考えられる．
Mention ネットワークを単純グラフ化して分析すると，返信の繰り返しによって構築されるユーザ間コミュニケーシ

ョンを考慮できないため，入次数の場合には多くのユーザから引用される著名人や，有益な発言をしたことで一時的に多くのユーザから引用されたユーザが，出次数の場合には多くのユーザに情報をまき散らすユーザが分析対象となる．しかし，これらのユーザは直接フォロワーと交流をすることが少なく，高コリンクノードになりにくいと推測される.
しかし，多重グラフを維持して解析することにより，特に出次数において，返信のやり取りを頻繁に行うような高頻度
コミュニケーションユーザが高次数ノードとして得られる．
これらのユーザは，フォロワーとの直接的なやり取りが頻繁に行われることから高コリンクノードになりやすいと考えられる．
この仮説を検証するため，多重 Mention ネットワークを
Reply（返信）ネットワークと Retweet（引用）ネットワー
クに分割し，多重 Mention ネットワークに対する Reply ネ

5― 17 ―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

表 2 各種 NW の入次数上位の入次数上位 1000 ノード間の Jaccard 係数

[謝辞]
謝辞]

Table 2 Jaccard Coefficient between Set of Top 1000
InIn-degree Nodes of each Networks
Reply NW
Retweet NW
多重 Mention NW
0.112
0.3
0.355

本研究を遂行するに当たり，ツイートの収集を協力して頂
いた，クックパッド株式会社の兼山元太氏に感謝します．また，本研究はNTTとの共同研究および，科研費(22500133) の助成を受けた．

表 3 各種 NW の出次数上位の出次数上位 1000 ノード間の Jaccard 係数[1]H.Kwak, C.Lee, H.Park, and S.Moon,“What isTwitter, a social network or a news media? “, In
Proceedings of the 19th international conference on
World wide web, pp.591-600. ACM,(2010).
[2] 鳥海不二夫，栗原聡，榊剛史，風間一洋，野田五十樹，“震災がもたらしたソーシャルメディアの変化”，第 7 回
ネットワークが創発する知能研究会研究報告要旨集
pp.41-46,(2011).
[3]R.Albert, and A.L.Barabási,"Statistical mechanics ofcomplex networks," Reviews of Modern Physics ,vol. 74,
pp. 47-97,(2002).
[4]A.Azquez. “Growing network with local rules:
Preferentialattachment, clustering hierarchy, anddegree correlations”.Physical Review E, Vol. 67, No. 5, pp.
56104,(2003).
[5]J.Goldenberg, B.Libai, and E.Muller, “Talk of the
network: A complex systems look at the underlying
processofword-of-mouth”,
MarketingLetters,
12:211-223,( 2001).
[6]小出明弘，斉藤和巳，鳥海不二夫，風間一洋，“フォロー
類似度による Twitter 高次数ユーザの関係分析”電子情報通信学会技術研究報告 Vol.111 No.427 pp.37-42,(2012).
[7] K.Ohara, K.Saito, M.Kimura, and H.Motoda, "Effectof In/Out-Degree Correlation on influence Degree of Two
Contrasting Information Diffusion Models," In
Proceedings of the 2012 International Conference on
Social Computing, Behavioral Modeling, and Prediction,
pp. 131-138,( 2012).

[文献］

Table 3 Jaccard Coefficient between Set of Top 1000
OutOut-degree Nodes of each Networks
Reply NW
Retweet NW
多重 Mention NW
0.39
0.033
0.394
394
ットワーク，Retweet ネットワークの高次数ノード集合の類
似度を分析する．
表 2，表 3 に多重 Mention ネットワークに対する Reply・Retweet ネットワークの入次数・出次数上位 1000 ノード集
合間の類似度を示す．類似度には，先述の Jaccard 係数を用いた．表から，多重 Mention ネットワークの高入次数ノード集合が Retweet ネットワークと，多重 Mention ネットワ
ークの高出次数ノードが Reply ネットワークと類似度が高い．このことから，多重 Mention ネットワークの高出次数
ノードが Reply を頻繁に行う高頻度コミュニケーションユーザであることが示唆される．
現実世界の複雑な関係を単純グラフで簡潔に表すことは，
ネットワーク構造の概要を把握するために有用である．しかし，現実のネットワーク構造においては，本稿で指摘した「返信」や「引用」のように，一見同じに見えるノード間の関係
が，複数の意味や役割を持つことが多い．このような場合，単純グラフでの解析は不十分であり，ユーザ間の関係の強弱を扱うことができる多重グラフでの分析が有効である．

6. おわりに
本論文では，ネットワーク内で中心的な役割を果たしていると考えられる高次数ノードを対象に，単純グラフと多重グ
ラフの違いについて分析した．具体的には，単純グラフであるフォローネットワークと多重グラフであるMentionネッ
トワーク，そしてそれを単純化した場合の3つのネットワー
クの基本統計量を示し，単純グラフのコリンク構造を解析するための手法を，多重グラフ対応に拡張した手法を提案した．
さらに，提案手法を多重グラフであるMentionネットワークに適用し，単純グラフ化したネットワークに従来手法を適用した場合との分析結果の違いを調査した．その結果，単純グ
ラフ化するとフォローネットワークに見られるようなコリンク構造が得られなかったが，多重グラフとして評価することにより，頻繁にメッセージを交換しているような高頻度コ
ミュニケーションユーザ検出することができた．
今後の課題として，多重リンクを有するネットワークについて，より詳細な分析を行うことがあげられる．特に，各ノードの多重度の分布や，ネットワーク全体での多重度を考慮したコミュニティの抽出など，単純グラフ化されたネットワークで定義された分析手法を多重グラフに拡張することにより，多重グラフとして分析しなければわからない特徴を抽出する．また，得られた知見をもとにユーザの特徴を踏まえた成長モデルやRetweet，Hashtagを情報拡散現象と仮定した情報拡散モデルを構築し，その有効性を評価する．

小出 明弘 Akihiro KOIDE
静岡県立大学大学院経営情報イノベーション研究科修士課
程在学中．複雑ネットワークの研究に従事．電子情報通信学会，人工知能学会各学生会員．

斉藤 和巳 Kazumi SAITO

静岡県立大学経営情報学部教授．1985 慶応義塾大学理工学
部数理科学科数学専攻卒業，1998 東京大学博士（工学）．複雑ネットワークの研究に従事．情報処理学会，電子情報通信
学会，人工知能学会，日本神経回路学会，日本応用数理学会，
日本行動計量学会各会員．

風間 一洋 Kazuhiro KAZAMA

日本電信電話株式会社未来ねっと研究所主任研究員．1988
京都大学大学院工学研究科精密工学専攻修士課程修了．同年
日本電信電話(株)入社．2005 京都大学大学院情報学研究科シ
ステム科学専攻博士課程修了．博士（情報学）．Web 情報検索，Web マイニングの研究に従事．情報処理学会，人工知能学会，日本ソフトウェア科学会，ACM 各会員．

鳥海 不二夫 Fujio TORIUMI東京大学工学研究科准教授．2004 東京工業大学大学院理工学研究科機械制御システム工学専攻博士課程修了．感性工学，
エージェントベースシミュレーション，人工市場などの研究に従事．電子情報通信学会，人工知能学会各会員．博士(工学)．

6― 18 ―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月