(57)【特許請求の範囲】
【請求項１】
複数のデータを各々表す複数のノードと、前記ノード間の隣接関係を各々表す複数のリンクとからなるネットワークから、所定以上の稠密度を有する部分ネットワークを抽出するネットワークコア抽出方法であって、
前記ネットワークに属する前記ノードを表すノードリスト、前記リンクをなす一対のノードであるノード対を表すリンクリスト、および、前記ネットワークのコア部の稠密度を制御するパラメータである次数ｋを受け付けるデータ入力処理と、
前記リンクの各々について当該リンクを構成する前記ノード対の両方に共通して隣接する前記ノードの数である共通隣接ノード数を算出し、前記リンクごとの前記共通隣接ノード数を求める共通隣接ノードカウント処理と、
前記リンクリスト、および、前記共通隣接ノードカウント処理で求めた前記リンクごとの前記共通隣接ノード数を基に、前記共通隣接ノード数がｋ−２より小さい前記リンクを削除対象リンクとして前記ネットワークから削除し、前記削除対象リンクの総数、および、前記削除対象リンクを削除した後に残った新たなリンクリストを出力するリンク削除処理と、
前記ネットワークの前記ノードリスト、および、前記リンク削除処理で出力された前記新たなリンクリストを基に、前記リンクをひとつも持たないノードである孤立ノードを当該ノードリストから削除し、削除した後に残った新たなノードリストを出力するノード削除処理と、
前記リンク削除処理で出力した前記削除対象リンクの総数がゼロより大きいか否かを判定し、当該削除対象リンクの総数がゼロより大きい場合は、前記リンク削除処理で出力した前記新たなリンクリスト、前記ノード削除処理で出力した前記新たなノードリスト、および、前記次数ｋを用いて再び前記共通隣接ノードカウント処理、前記リンク削除処理、および、前記ノード削除処理を行い、ゼロの場合は、前記リンク削除処理で出力した前記新たなリンクリスト、および、前記ノード削除処理で出力した前記新たなノードリストを出力するコア条件判定処理と、
を有することを特徴とするネットワークコア抽出方法。
【請求項２】
複数のデータを各々表す複数のノードと、前記ノード間の隣接関係を各々表す複数のリンクとからなるネットワークから、所定以上の稠密度を有する部分ネットワークを抽出するネットワークコア抽出装置であって、
前記ネットワークに属する前記ノードを表すノードリスト、前記リンクをなす一対のノードであるノード対を表すリンクリスト、および、前記ネットワークのコア部の稠密度を制御するパラメータである次数ｋを受け付ける入力部と、
前記リンクの各々について当該リンクを構成する前記ノード対の両方に共通して隣接する前記ノードの数である共通隣接ノード数を算出し、前記リンクごとの前記共通隣接ノード数を求める共通隣接ノードカウント部と、
前記リンクリスト、および、前記共通隣接ノードカウント処理で求めた前記リンクごとの前記共通隣接ノード数を基に、前記共通隣接ノード数がｋ−２より小さい前記リンクを削除対象リンクとして前記ネットワークから削除し、前記削除対象リンクの総数、および、前記削除対象リンクを削除した後に残った新たなリンクリストを出力するリンク削除処理部と、
前記ネットワークの前記ノードリスト、および、前記リンク削除処理で出力された前記新たなリンクリストを基に、前記リンクをひとつも持たないノードである孤立ノードを当該ノードリストから削除し、削除した後に残った新たなノードリストを出力する、ノード削除処理部と、
前記リンク削除処理で出力した前記削除対象リンクの総数がゼロより大きいか否かを判定し、当該削除対象リンクの総数がゼロより大きい場合は、前記リンク削除処理部で出力した前記新たなリンクリスト、前記ノード削除処理部で出力した前記新たなノードリスト、および、前記次数ｋを用いて再び前記共通隣接ノードカウント処理部、前記リンク削除処理部、および、前記ノード削除処理部に処理を行わせ、ゼロの場合は、前記リンク削除処理部で出力した前記新たなリンクリスト、および、前記ノード削除処理部で出力した前記新たなノードリスト出力するコア条件判定部と、
を有することを特徴とするネットワークコア抽出装置。
【請求項３】
請求項１に記載のネットワークコア抽出方法をコンピュータに実行させることを特徴とするネットワークコア抽出プログラム。
【請求項４】
請求項３に記載のネットワークコア抽出プログラムが記録されたことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノードと、このノード間の隣接関係を示すリンクとからなるネットワークから、所定以上の稠密度を有する部分ネットワークを抽出する、ネットワークコア抽出方法および装置、ネットワークコア抽出プログラムとそのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
例えば、ブログ、ウェブページ、電子図書、特許公報、論文などの要素からなるデータの集合について、集合の要素をノードとし、要素間に一定の関係があることをリンクとするネットワークとして表現できる。そして、これらのデータの集合に内在する主要コミュニティやトピックを抽出することが考えられる。
【０００３】
与えられたネットワーク（全体）から、ノードが密結合している部分ネットワークを抽出するにあたって、抽出対象となる部分ネットワークはコア部と呼ばれ、あるいは、コミュニティとも呼ばれている。このように、ネットワークから部分ネットワークを抽出する方法として、従来、「k-core分解法」（例えば、非特許文献１参照）および「k-cliqueコミュニティ抽出法」（例えば、非特許文献２参照）が知られている。
【０００４】
後記するように、まず、k-core分解法（以降、k-core法という。）は、計算量が少なく、効率的であるが、抽出されるコア部の粒度が荒く、詳細な構造を求めるには不向きであるという問題点があった。そして、k-cliqueコミュニティ抽出法（以降、k-clique法という。）は、詳細な（あるいは、詳細に過ぎる）構造を求めることができるが、計算量が大きいため、大規模ネットワークへ適用することが困難であるという問題があった。
【０００５】
k-core法（非特許文献１参照）では、コア部とは、与えられたネットワークの部分ネットワークであって、この部分ネットワーク内の各ノードがｋ個以上の隣接ノード、すなわちリンクで直接つながっているノードをその部分ネットワーク内に持つもののことである。なお、本説明においては、自ノードを含めてｋ個以上の隣接ノードを考慮するとの観点から、前記概念と実質的に全く同等ではあるが、ｋの基準をひとつずらした次の定義を用いる。すなわち、次数ｋのk-core（ｃ(ｋ)と表す）とは、部分ネットワーク内の各ノードがｋ−１個以上の隣接ノードをその部分ネットワーク内に持つものと定義する。ｋはコア部の稠密度を制御するパラメータであり、次数と呼ぶ。
【０００６】
より正確には、以下のように定義できる。今、ネットワークＧを、ノード集合Ｖおよびリンク集合ＥによってＧ＝(Ｖ，Ｅ)として定義する。ただし、ノード集合をＶ＝{１，…，Ｎ}で、リンク集合をＥ＝{ｅ１，…，ｅＭ}で表し、各リンクｅ∈Ｅは、ｅ＝{ｉ，ｊ}⊂Ｖ（ただしｉ≠ｊ）と表せるものとする。すなわち、自己リンクなしの無向ネットワークを対象とする。ここでＮは全ノード数、Ｍは全リンク数である。
【０００７】
ネットワークＧ＝(Ｖ，Ｅ)において、ノードｉが隣接するノード集合を次式で表す。
【０００８】
【数１】
0004714080.tif 000002
【０００９】
ネットワークＧのk-coreとは、与えられた次数ｋに対して、次の条件を満たすノード集合Ｖｃ(ｋ)⊂Ｖと、リンク集合Ｅｃ(ｋ)⊂Ｅから構成されるＧの部分ネットワークＣ(ｋ)＝(Ｖｃ(ｋ)，Ｅｃ(ｋ))のことである。
【００１０】
【数２】
0004714080.tif 000003
【００１１】
【数３】
0004714080.tif 000004
【００１２】
ここで、|Ａ|は集合Ａの要素数を表す。
これは各ノードを「人」、ノード間のリンクを互いに「友達」であるという関係を表すとすると、部分ネットワーク内ではすべての人が、ｋ−１人以上の友達をその部分ネットワーク内に持つ、ということである、と解釈することができる。一般に、得られたk-coreであるＣ(ｋ)は連結とは限らない。与えられたネットワークからｋを指定してk-coreを抽出し、さらに連結成分Ｃ８(ｋ)(ｓ＝１，２，３，‥，Ｓｃ(ｋ))に分解することが、k-core法であり、各ＣＳ(ｋ)をk-coreコミュニティと呼ぶ。ここで、ＳＣ(ｋ)はＣ(ｋ)を連結成分に分解した際の連結成分の個数を表す。
【００１３】
図１は、k-coreコミュニティの一例を示す模式図である。
この例では、一番外側の枠内のネットワーク全体に対し、１つ内側の枠内の部分ネットワークが次数３のk-coreに対応しており、これは連結であるので、同時に次数３のk-coreコミュニティでもある。さらに内側の２つの枠内のそれぞれの部分ネットワークが次数４のk-coreコミュニティに対応している。
【００１４】
一方、k-clique法によるCFinder（非特許文献２参照）では、cliqueを利用したコア抽出法である、k-clique法を提案している。ここでcliqueとは、与えられたネットワークの部分ネットワークであって、この部分ネットワーク内のノードがすべてお互いにリンクでつながっている、すなわち完全グラフとなっているもののことである。ノード数がｋであるcliqueをk-cliqueと呼びＱ(ｋ)と表す。一般にcliqueのうち、これ以上ノードを加えるともはやcliqueにならないものを極大cliqueと呼ぶ。２つのk-cliqueが隣接するとは、２つのk-cliqueに共通して出現するノード数がｋ−１であることである。これは各ノードを「人」、ノード間のリンクを互いに「友達」であるという関係を表すとすると、部分ネットワーク内ではすべての人が互いに友達である、と解釈できる。k-clique法では、与えられたネットワークの極大cliqueを全て抽出する。さらに、これら抽出した極大clique全体からノード数がｋであるもの(すなわちk-clique）全体を考え、これらの中で隣接するk-cliqueをすべてつなげたものをk-cliqueコミュニティと呼び、各ｋについてk-cliqueコミュニティＲＳ(ｋ)(ｓ＝１，２，３，…，ＳＲ(ｋ))を抽出する。ここで、ＳＲ(ｋ)はk-cliqueコミュニティの個数を表す。またここで、ＲＳ(ｋ)全体の和集合をＲ(ｋ)で表す。
【００１５】
図２は、k-cliqueコミュニティの一例を示す模式図である。この例では、２つの次数が５のcliqueが４個のノードを共有しており、合わせて１つのk-cliqueコミュニティを構成している。
【００１６】
【非特許文献１】Stanley Wasserman and Katherine Faust, "Social Network Analysis", Cambridge University Press, p.266, 1994.
【非特許文献２】G. Palla, I. Derenyl, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society", Nature 435, 2005, 814-818.
【発明の開示】
【発明が解決しようとする課題】
【００１７】
k-core法（非特許文献１参照）では、ネットワーク上の各ノードについて、ｋ−１個以上の隣接ノードを持つという条件を満足するかどうかを調査し、条件を満足しないノードを削除する、という操作を再帰的に行うことによって計算することができるため、高速に計算可能で効率的である。しかし、このk-core法では、隣接ノード数のみが考慮の対象であり、ノード間の関係の強さを考慮しないため、互いの関連が希薄なノードを含んで部分ネットワークのサイズが大きくなりすぎる傾向があり、したがって粒度の荒い抽出となるため、詳細な構造を求めるには不向きであるという問題点があった。
【００１８】
k-clique法（非特許文献２参照）では、極大cliqueをすべて列挙することは、NP-hard（ＮＰ困難）問題であり、最適解を求めることは、非常に困難である。つまり、ネットワークが大規模になれば極大clique数が爆発的に大きくなるため、k-clique法によるCFinderでは、計算量が膨大になって、大規模なネットワークには実質的に適用できない問題点があった。
【００１９】
前記従来技術の問題点を鑑み、本発明は、大規模なネットワークから、k-clique法に匹敵する精度と、k-core法に準ずる効率の良さとを併せ持って、ネットワークのコア部を抽出できるネットワークコア抽出方法および装置、ネットワークコア抽出プログラムとそのプログラムを記録した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２０】
前記課題を解決するため、請求項１に記載のネットワークコア抽出方法は、複数のデータを各々表す複数のノードと、これらノード間の隣接関係を各々表す複数のリンクとからなるネットワークから、所定以上の稠密度を有する部分ネットワークを抽出するネットワークコア抽出方法であって、このネットワークに属するノードを表すノードリスト、リンクをなす一対のノードであるノード対を表すリンクリスト、および、ネットワークのコア部の稠密度を制御するパラメータである次数ｋを受け付けるデータ入力処理と、リンクの各々についてこれらリンクを構成するノード対の両方に共通して隣接するノードの数である共通隣接ノード数を算出し、リンクごとの共通隣接ノード数を求める共通隣接ノードカウント処理と、リンクリスト、および、共通隣接ノードカウント処理で求めたリンクごとの共通隣接ノード数を基に、共通隣接ノード数がｋ−２より小さいリンクを削除対象リンクとしてネットワークから削除し、削除対象リンクの総数、および、削除対象リンクを削除した後に残った新たなリンクリストを出力するリンク削除処理と、ネットワークのノードリスト、および、リンク削除処理で出力された新たなリンクリストを基に、リンクをひとつも持たないノードである孤立ノードをノードリストから削除し、削除した後に残った新たなノードリストを出力するノード削除処理と、リンク削除処理で出力した削除対象リンクの総数がゼロより大きいか否かを判定し、この削除対象リンクの総数がゼロより大きい場合は、リンク削除処理で出力した新たなリンクリスト、ノード削除処理で出力した新たなノードリスト、および、次数ｋを用いて再び共通隣接ノードカウント処理、リンク削除処理、および、ノード削除処理を行い、ゼロの場合は、リンク削除処理で出力した新たなリンクリスト、および、ノード削除処理で出力した新たなノードリスト出力するコア条件判定処理と、を有することを特徴とする。
【００２１】
かかる手順によれば、共通隣接ノード処理で、リンクの各々についてこれらリンクを構成するノード対の両方に共通して隣接するノードの数である共通隣接ノード数を算出し、リンクごとの共通隣接ノード数を求め、リンク削除処理およびノード削除処理で、この共通隣接ノード数がｋ−２より小さいリンクおよびノードをネットワークから削除し、これらの処理を繰り返して、部分ネットワークを抽出している。
【００２２】
前記課題を解決するため、請求項２に記載のネットワークコア抽出装置は、複数のデータを各々表す複数のノードと、これらノード間の隣接関係を各々表す複数のリンクとからなるネットワークから、所定以上の稠密度を有する部分ネットワークを抽出するネットワークコア抽出装置であって、このネットワークに属するノードを表すノードリスト、リンクをなす一対のノードであるノード対を表すリンクリスト、および、ネットワークのコア部の稠密度を制御するパラメータである次数ｋを受け付けるデータ入力部と、リンクの各々についてこれらリンクを構成するノード対の両方に共通して隣接するノードの数である共通隣接ノード数を算出し、リンクごとの共通隣接ノード数を求める共通隣接ノードカウント部と、リンクリスト、および、共通隣接ノードカウント部で求めたリンクごとの共通隣接ノード数を基に、共通隣接ノード数がｋ−２より小さいリンクを削除対象リンクとしてネットワークから削除し、削除対象リンクの総数、および、削除対象リンクを削除した後に残った新たなリンクリストを出力するリンク削除処理部と、ネットワークのノードリスト、および、リンク削除処理部で出力された新たなリンクリストを基に、リンクをひとつも持たないノードである孤立ノードをノードリストから削除し、削除した後に残った新たなノードリストを出力するノード削除処理部と、リンク削除処理部で出力した削除対象リンクの総数がゼロより大きいか否かを判定し、この削除対象リンクの総数がゼロより大きい場合は、リンク削除処理部で出力した新たなリンクリスト、ノード削除処理部で出力した新たなノードリスト、および、次数ｋを用いて再び共通隣接ノードカウント処理部、リンク削除処理部、および、ノード削除処理部で処理を行わせ、ゼロの場合は、リンク削除処理部で出力した新たなリンクリスト、および、ノード削除処理部で出力した新たなノードリストを出力するコア条件判定処理部と、を有することを特徴とする。
【００２３】
かかる構成によれば、共通隣接ノード処理部で、リンクの各々についてこれらリンクを構成するノード対の両方に共通して隣接するノードの数である共通隣接ノード数を算出し、リンクごとの共通隣接ノード数を求め、リンク削除処理部およびノード削除処理部で、この共通隣接ノード数がｋ−２より小さいリンクおよびノードをネットワークから削除し、これらの処理を繰り返して、部分ネットワークを抽出している。
【発明の効果】
【００２４】
本発明によれば、例えば、ブログ、ウェブページ、電子図書、特許公報、論文など、ノードとして扱いうるデータと、これらノード相互の関係（隣接関係）を示すリンクからなるネットワークから、所定以上の稠密度を有する部分ネットワーク（コア部）を、高速かつ高精度に抽出できる。これにより、例えば、大規模なノード集合群に内在する主要コミュニティやトピックを、高速かつ高精度に抽出することができる。
【発明を実施するための最良の形態】
【００２５】
本発明による一実施形態による方法（本説明においてk-dense法という）は、概略を説明すると、例えばハイパーリンクによる参照があるウェブページ群において、各ページをノード（頂点）、ハイパーリンクをリンク（辺）と見なしたときに構成されるようなネットワーク（グラフ）を考え、比較的にリンクが密集する部分（これをコア部と呼ぶ）には、例えば共通的なホットな話題など、重要な情報が集中して存在すると考え、そのコア部の抽出を試みる一方法である。そこで、k-dense法では、コア部の稠密度を制御するパラメータである次数ｋに対して、k-denseと呼ばれる条件に基づき不要リンクの削除を行ない、その結果孤立ノード（リンクを１つも持たないノード）となったノードの削除を行い、削除するノードとリンクとが存在しなくなるまでこれらを交互に繰り返すと共に、前記ネットワークにコア部が存在しなくなるまで、パラメータである次数ｋの値をｋ＝２からｋ＝ｋ＋１として順次変化させてコア部を抽出する。
【００２６】
まず、k-denseコミュニティの基本概念について詳細に説明する。そして、k-denseコミュニティの抽出アルゴリズムについて説明する。
【００２７】
＜k-denseコミュニティの定義＞
k-denseコミュニティの概念では、与えられたネットワークにおいて、隣接する（すなわちリンクで直接結ばれている）任意のノード対の共通隣接ノードと、これらノード対の両方に対し隣接するノードを共通隣接ノードと称する。そして、共通隣接ノードを所定数以上有するノード対と、このノード対を結ぶリンクとからなる部分ネットワークを、k-denseコミュニティと称する。
比喩すれば、これは各ノードが「人」を表し、ノード間のリンクが互いに「友達」であるという関係を表すとすると、この互いに友達である二人の共通隣接ノードとは、この二人に共通する「友達」を意味する。
【００２８】
ネットワークＧのk-denseであるＤ(ｋ)とは、ネットワーク(全体)Ｇの部分ネットワークのひとつであって、Ｄ(ｋ)内の隣接する任意のリンク（すなわちノード対）が、(ｋ−２)個以上の共通隣接ノードをその部分ネットワーク内に有する部分ネットワークである、と定義する。すなわち、その部分ネットワーク内においては、互いに友達である任意の二人は必ず(ｋ−２)人以上の共通の友達を持つということである。
【００２９】
より正確には次の通り定義できる。
まず、ネットワークＧ＝(Ｖ，Ｅ)において、リンクｅ＝{ｅ１，ｅ２}∈Ｅの共通隣接ノードの集合Ｆ２Ｇ(ｅ)は、次式で表せる。
【００３０】
【数４】
0004714080.tif 000005
【００３１】
つまり、k-denseは、与えられた次数（整数）ｋに対し、次の条件を満たすノード集合ＶＤ(ｋ)⊂Ｖとリンク集合ＥＤ(ｋ)＞⊂Ｅとから構成されるネットワークＧの部分ネットワークＤ(ｋ)＝（ＶＤ(ｋ)，ＥＤ(ｋ)）のことである。
【００３２】
【数５】
0004714080.tif 000006
【００３３】
【数６】
0004714080.tif 000007
【００３４】
ここでは、リンクｅ＝|ｅｌ，ｅ２|∈Ｅを、ノード集合ｅ＝|ｅｌ，ｅ２|⊂Ｖとみなしている。一般に、得られたk-denseは連結には限られない。k-dense法は、与えられたネットワークからk-denseを抽出し、さらに連結成分ＤＳ(ｋ)（ｓ＝１，２，３，…，ＳＤ(ｋ)）に分解する方法であり、各ＤＳ(ｋ)をk-denseコミュニティと呼ぶ。ここで、ＳＤ(ｋ)はＤ(ｋ)を連結成分に分解した際の連結成分の個数を表す。
【００３５】
図３は、k-denseコミュニティの一例を示す模式図である。
この例では、一番外側の枠内のネットワーク全体に対し、内側の枠内の各部分ネットワークが次数３のk-denseに対応している。
【００３６】
図４は、本発明による一実施形態のネットワークコア抽出装置の構成を示すブロック図である。
このネットワークコア抽出装置は、対象となるネットワークＧ＝（Ｖ，Ｅ）および、コア部の稠密度を制御するパラメータである次数ｋを入力として受け取る入力部１と、共通隣接ノード数をカウントする共通隣接ノードカウント部２と、共通隣接ノード数がｋ−２より小さいリンクを削除し、その際削除対象となったリンク数をＬ、削除後のリンクの集合をＥ’とするリンク削除処理部３と、孤立ノードを削除し、削除後のノード集合をＶ’とするノード削除処理部４と、Ｌ＞０かどうかを判定し、Ｌ＞０である場合はＧ＝Ｇ，＝(Ｖ’，Ｅ’)として共通隣接ノードカウント部２の処理へ、そうでない場合はＤ(ｋ)＝Ｇ，＝(Ｖ’，Ｅ’)として後述の出力部６の処理へ進めるコア条件判定部５と、Ｄ(ｋ)を出力する出力部６と、入力および途中結果を格納するデータ格納部７と、全体の制御を行う制御部８とを具備している。
【００３７】
このネットワークコア抽出装置は、典型的には、本実施形態で示す動作を行わせるためのプログラムを、コンピュータにロードし、実行させることによって実現できる。また、このプログラムを、記録媒体に記憶させておき、必要に応じて、このコンピュータにロードするようにしてもよい（いずれも図示せず）。
【００３８】
＜k-dense抽出アルゴリズム＞
k-denseは、対象となるネットワークに関するデータおよびコア部の稠密度を制御するパラメータとして次数ｋを入力として与えることによって、以下のように計算できる。なお、対象となるネットワークＧのデータ構造は、ノード集合Ｖおよびリンク集合ＥによってＧ＝（Ｖ，Ｅ）として与えられる。
【００３９】
ステップｄ０：  Ｇ＝(Ｖ，Ｅ)（対象となるネットワーク）、および、ｋ（コア部の稠密度を制御するパラメータ）を入力として与える。
ステップｄｌ：  対象となるネットワークＧの各リンク(すなわち、Ｅの要素)に対し、共通隣接ノード数をカウントする。
ステップｄ２：  ステップｄｌで計算した共通隣接ノード数がｋ−２より小さいリンクを削除する。その結果得られたリンク全体の集合をＥ’とする。削除対象となったリンク数をＬとする。
ステップｄ３：  ステップｄ２でリンクを削除した結果、孤立ノードとなったノードを削除する。その結果得られたノード全体の集合をＶ’とする。
ステップｄ４：  ステップｄ２で削除されたリンク数がゼロより大であれば、当初与えられたＧ＝（Ｖ，Ｅ）の代わりに、ステップｄ２およびステップｄ３で得られたＧ＝(Ｖ’，Ｅ’)を用いて、ステップｄｌ以降を繰り返す。そうでなければ（ステップｄ２で削除されたリンク数がゼロであれば）、ステップｄ２およびステップｄ３で得られたＤ(ｋ)＝Ｇ’＝(Ｖ’，Ｅ’)を出力し、計算を終了する。
【００４０】
図５は、k-dense抽出手順を示すフローチャートである（適宜、図４参照）。
まず、ネットワークのデータおよびパラメータを入力する。具体的には、対象となるネットワークＧ＝(Ｖ，Ｅ)のデータ、および、コア部の稠密度を制御するパラメータである次数ｋを入力部１から入力する（ステップＳ１）。
【００４１】
次に、共通隣接ノードカウント部２は、各リンク（すなわちＥの各要素）に対して、共通隣接ノード数をカウントする（ステップＳ２）。
【００４２】
次に、リンク削除処理を行う（ステップＳ３）。具体的には、リンク削除処理部３は、Ｅの各要素であるリンクのうち、共通隣接ノード数がｋ−２より小さいリンクを削除する。そして、その際削除対象となったリンク数をＬ、削除後のリンクの集合をＥ’とする。
次に、ノード削除処理を行う（ステップＳ４）。具体的には、ノード削除処理部４は、各ノード（すなわちＶの各要素）のうち、リンク削除処理部３による処理の結果、孤立ノード（すなわちひとつもリンクを持たないノード）となったものを削除し、削除後のノード集合をＶ’とする。
【００４３】
次に、コア条件を判定する。すなわち、Ｌ＞０であるか否かを判定する。具体的には、コア条件判定部５は、リンク削除処理部３によって得られたＬについて、Ｌ＞０か否かを判定する（ステップＳ５）。
【００４４】
Ｌ＞０である場合（ステップＳ５のＹｅｓ）、Ｇ＝Ｇ’＝(Ｖ’，Ｅ’)とおきなおして、ステップＳ２以下の処理を繰り返す。そうでない場合（ステップＳ５のＮｏ）、出力部６がＤ(ｋ)＝Ｇ’＝(Ｖ’，Ｅ’)を出力して（ステップＳ６）、処理を終了する。
【００４５】
＜簡単なネットワークによる例＞
図６は、小規模なネットワークに対しk-dense抽出を行った実行例を段階的に示す説明図である。
まず、図６（１）に示すように、入力として１６個のノード、２８本のリンクからなるネットワークが与えられる。また、コア部の稠密度を制御するパラメータである次数ｋは、ｋ＝４とする。図６（２）に、与えられたネットワークの接続関係を模式的に示す。次に、図６（３）に、各リンクに対し、共通隣接ノード数をカウントしたものを示す。図６（４）に、これらの数値に従って、共通隣接ノード数がｋ−２＝２より小さいリンクを削除（図中では点線で表示）したものを示し、このとき削除されたリンク数はＬ＝１０である。次に、図６（５）に、リンク削除の結果、孤立ノードを削除した結果を示す（削除されたノードは、二点鎖線でのみ囲んで表示）。この時点で削除されたリンク数はＬ＝１０＞０であるので、図６（６）に示すように、再び共通隣接ノード数をカウントする。図６（７）に、その結果、共通隣接ノード数がｋ−２＝２より小さいリンクを削除（図中では点線で表示）したものを示し、図６（８）に、さらにその結果、孤立ノードを削除したものを示す。この時点で削除されたリンク数はＬ＝１＞０であるので、再び共通隣接ノード数をカウントする処理に戻るが、その結果削除対象となるリンクは存在せず、Ｌ＝０となるので、図６（８）に示すネットワークを出力して処理終了となる。
【００４６】
＜Ｄ(ｋ)の計算結果を用いた、Ｄ(ｋ＋１)の計算）＞
前記したように、k-dense抽出アルゴリズムは、固定された１つのｋに対するk-denseを計算するものであるが、Ｄ(ｋ＋１)⊆Ｄ(ｋ)という関係があるので、Ｄ(ｋ＋１)を求める際に、既にＤ(ｋ)が計算されている場合は、Ｇの代わりにＤ(ｋ)をk-dense抽出アルゴリズムの入力として与えれば、Ｇそのものを入力として与えた場合に較べてより速くＤ(ｋ＋１)が求まる。また、Ｒ(ｋ)⊆Ｄ(ｋ)であるため、まず部分ネットワークＤ(ｋ)を抽出し、対象となるネットワークのサイズを小さくすることによってk-clique抽出の効率化を実現することもできる。
【００４７】
図７は、k-core、k-dense、k-cliqueを比較して示す模式図である。
このように、一般にＱ(ｋ)⊆Ｄ(ｋ)⊆  Ｃ(ｋ)が成り立つ。この事実を利用すれば、Ｄ(ｋ)を求める際に、既にＣ(ｋ)が計算されている場合は、Ｇの代わりにＣ(ｋ)をk-dense抽出アルゴリズムの入力として与えれば、Ｇそのものを入力として与えた場合に較べてより速くＤ(ｋ)が求まる。
【００４８】
＜ランクｈの一般化k-denseへの拡張＞
なお、前記k-denseコミュニティの定義において、k-denseとは、対象となるネットワークＧの部分ネットワークＤ(ｋ)であって、任意のリンクが、(ｋ−２)個以上の共通隣接ノードをＤ(ｋ)内に持つもの、と定義された。ここで、任意のリンクは、任意の２-cliqueと言い換えることができる。同様にして、ランクｈ(ｈ≦ｋ)の一般化k-denseとしてＤ(ｋ；ｈ)を、Ｇの部分ネットワークであって、任意のh-cliqueが、(ｋ−ｈ)個以上の共通隣接ノードをＤ(ｋ；ｈ)内に持つものと定義することができる。
【００４９】
より正確には以下のようになる。まず、ネットワークＧ＝(Ｖ，Ｅ)に含まれる、任意のh-cliqueであるＱ(ｈ)の共通隣接ノードの集合ＦｈＧ(Ｑ(ｈ))を以下で表す。
【００５０】
【数７】
0004714080.tif 000008
【００５１】
また、Ｇの任意のリンクは２-cliqueであるから、k-cliqueの定義を用いれば、式（５）および式（６）で定義したk-denseである部分ネットワークＤ(ｋ)の条件を次のように表現できる。
【００５２】
【数８】
0004714080.tif 000009
【００５３】
すなわち、隣接するノードペアＱ(２)はｋ−２個以上の共通ノードと隣接することになる。この考え方を拡張すれば、今、１≦ｈ＜ｋに対し、ランクｈ(ｈ≦ｋ)の一般化k-denseであるＤ(ｋ；ｈ)は、次のように表現できる。
【００５４】
【数９】
0004714080.tif 000010
【００５５】
同様に、Ｄ(ｋ；ｈ)の連結成分として、ランクｈの一般化k-denseコミュニティもＤＳ(ｋ；ｈ)(ｓ＝１，２，３，…，ＳＤ(ｋ；ｈ))と定義できる。ここでＳＤ(ｋ；ｈ)は連結成分の個数である。明らかに、Ｄ(ｋ；１)はk-coreの定義、すなわち、Ｄ(ｋ；１)＝Ｃ(ｋ)に他ならない。
【００５６】
一方、ｈ＝ｋ−１とすれば、Ｄ(ｋ；ｋ−１)の任意のノード１は、少なくとも１つのk-cliqueを構成するノードとなることは容易に確認できる。よって、ランク(ｋ−１)の一般化k-denseはk-clique全体の和集合であるＲ(ｋ)と一致する。つまり、Ｄ(ｋ；ｋ−１)＝Ｒ(ｋ)である。従って、一般化k-denseＤ(ｋ；ｈ)は、k-coreＣ(ｋ)とk-clique全体の和集合であるＲ(ｋ)とを補間するひとつの概念と考えられる。
【００５７】
定義から明らかなように、ランク(ｋ−１)の一般化k-denseコミュニティと共通ノードを１つ以上持つk-cliqueコミュニティの和集合とは一致する。一方、発明者の予備実験では、ランク２とランク(ｋ−１)の一般化k-denseコミュニティは多くの場合で一致した。k-cliqueコミュニティの抽出と同様に、ランク(ｋ−１)の一般化k-denseを求めるにはk-clique抽出が必要となり、多くの計算量が必要となる。よって、本実施形態では、大規模ネットワークへの適用の観点から、ランク２のk-denseに焦点を絞って説明を行う。以降、ランク２のk-denseを簡単にk-denseと呼ぶ。
【００５８】
＜実験による評価＞
次に、実験に用いた３種のネットワークと、各方法で抽出されたコア部の特徴を調べる評価尺度とについて説明する。その後、これらネットワークを用いた実験結果を示し、考察する。
【００５９】
＜実験設定＞
実験には、ブログのトラックバック（ＴＢ）からなるネットワーク、PallaらがCFinder評価に使った単語連想ネットワーク、および、インターネット上のフリーの百科事典であるWikipedia（登録商標）（英語版）の記事間に張られた共参照ネットワークを用いた。
【００６０】
表１に上記３つのネットワークの基本統計量を示す。
【００６１】
【表１】
0004714080.tif 000011
【００６２】
実験では、本発明（k-dense法）、k-core法、およびk-clique法（CFinder）で抽出した各種コミュニティの特徴を比較評価した。すなわち、各ｋでのＣ(ｋ)＝｛ｃｓ(ｋ)：１≦ｓ(ｋ)≦Ｓｃ(ｋ)）、Ｄ(ｋ)＝{ＤＳ(ｋ)：、１≦ｓ(ｋ)≦ＳＤ(ｋ)）、Ｒ(ｋ)＝{ＲＳ(ｋ)：１≦ｓ(ｋ)≦ＳＲ(ｋ)）の比較である。
【００６３】
評価尺度は、コミュニティ全体のサイズ、最大コミュニティのサイズ、コミュニティ数、および各コミュニティのサイズの分布を調べるための正規化エントロピーの４つである。以下に評価尺度の詳細について述べる。
【００６４】
今、ＸでＣ(ｋ)、Ｄ(ｋ)、又は、Ｒ(ｋ)のいずれかを表し、ＸＳで対応するコミュニテイ（すなわち、各連結成分）を表すものとする。一般に集合Ｙのサイズ（要素数）を|ＶＹ|で表すことにすると、各コミュニティのサイズは|ＶＸＳ|、コミュニティ全体のサイズは、コミュニティの和集合に含まれるノード数であって|ＶＸ|となる。なお、k-cliqueコミュニティでは、１つのノードが複数コミュニティに属すこともあるが、それらの重複カウントは避けることとする。最大コミュニティのサイズはmax{|ＶＸＳ|}であり、コミュニティ数はＳＸである。正規化エントロピーは次式で定義する尺度とする。
【００６５】
【数１０】
0004714080.tif 000012
【００６６】
すなわち、正規化エントロピーという尺度は、各コミュニティのサイズ|ＶＸＳ|が均等ならば１に近づき、逆に、ばらつきが大きければ０に近くなる、というものである。なお、Ｓｘ≧２のときのみε(Ｘ)は定義されるとする。
【００６７】
＜第１例：ブログＴＢネットワークでの評価＞
ブログＴＢネットワークに対して、本実施形態（k-dense法）、k-core法、および、k-clique法（CFinder）を、次数ｋを変えながら、適用した。結果、コミュニティが存在した最大次数は、k-dense法とCFinderではｋ＝１５で一致し、k-core法ではｋ＝２０となった。
以下に比較の詳細について述べる。
【００６８】
図８は、コアの次数ｋに対するコミュニティ全体（すなわち、コア部全体）のサイズを示すグラフである。
任意のｋにおいて、k-dense法とCFinderが抽出したコミュニティ全体のサイズはほぼ等しい。これらと比較し、k-core法で抽出されたコミュニティ全体のサイズはかなり大きいことが分かる。
【００６９】
図９は、コアの次数ｋに対する最大コミュニティのサイズを示すグラフである。
７≦ｋ≦１３の範囲では、k-dense法とCFinderの最大コミュニティのサイズはほぼ等しい。ここでも、k-core法で抽出された最大コミュニティのサイズはかなり大きく、図８に示す結果と組み合わせることにより、k-core法では多くのノードが最大コミュニティに集中していることが分かる。
【００７０】
図１０は、コアの次数ｋに対するコミュニティ数を示すグラフである。
ｋ≦６程度までk-dense法が抽出したコミュニティ数は、CFinderと比較して、ある程度少ない結果となっている。一方、ｋが大きくなるにつれて両者の差が小さくなっていることが分かる。ところがｋ≦６のときCFinderが抽出したコミュニティ数は１００を越え、コミュニティがかなり細分化されている。一般に、抽出したコミュニティ数が非常に多く、細分化されていると、例えば、ウェブページ群の分類を例に取ると、分類すべきカテゴリ数が多くかつ分類が細かいことになり、ユーザがカテゴリを利用しにくい、など、扱いづらい場合も想定できる。一方、k-core法で抽出したコミュニティ数は、最大でも１０程度で、かつ、極端にサイズの大きなコミュニティが存在するため、逆に分類の粒度が荒すぎて、詳細なネットワーク構造を分析するには限界が起こることも想定できる。
【００７１】
図１１は、コアの次数ｋに対する正規化エントロピーを示すグラフである。
ここではk-dense法とCFinderが複数コミュニティを抽出した３≦ｋ≦１４で比較している。この範囲においてk-dense法とCFinderは、比較的に均等なサイズのコミュニティ群を抽出しており、両者の間にあまり差はない。これに対してk-core法は、特にｋが小さいときにかなり偏りが大きいことが分かる。
【００７２】
このように、ブログＴＢでは、抽出されたコミュニティの特性のみを考えた場合、k-dense法はk-core法とくらべて、よりサイズの偏りが小さく比較的に均等なサイズのコミュニティ群を安定して抽出することが可能で、極端にサイズの大きなコミュニティを荒い粒度で抽出してしまうということがない。また、k-clique法とくらべて、抽出したコミュニティが細分化されてしまいコミュニティ数が極端に多くなってしまう、ということがなく、これらを合わせると、k-dense法はk-core法、k-clique法の両者に較べてよりバランスの取れた安定した抽出法であるといえる。
【００７３】
＜第２例：単語連想ネットワークでの評価＞
単語連想ネットワークに、本発明（k-dense法）、k-core法、および、k-clique法（CFinder）を適用した。ここで単語連想ネットワークとは、単語をノードとし、各単語に対して、その単語と意味的に近く、連想しやすい単語をリンクでつないだネットワークである。結果、コミュニティが存在した最大次数は、k-dense法とCFinderではｋ＝７で一致し、k-core法ではｋ＝８となった。
【００７４】
以下に比較の詳細について述べる。
図１２、図１３、および図１４は、各々、コアの次数ｋに対するコミュニティ全体のサイズ、最大コミュニティのサイズ、およびコミュニティ数を示すグラフである。
結果の傾向は、ブログＴＢネットワークへの各方法を適用した場合の結果と類似している。すなわち、図１２より、任意の次数ｋにおいてk-dense法とCFinderとで抽出するコミュニティ全体のサイズはほぼ完全に一致する。また、図１３より、ｋ＝４、５でk-dense法が抽出した最大コミュニティのサイズは、CFinderが抽出したものと比較して、ある程度大きい結果となっているが、図１４のコミュニティ数の結果と組み合わせれば、CFinderはコミュニティを数百から千近い程度にまで細分化してしまっていることが分かる。最後に、どのようにｋを選んでもk-core法では複数コミュニティへの分解ができず、最大の次数ｋ＝８でも数千ものノードが単一コミュニティに属すという、粒度の荒い抽出結果となった。
【００７５】
図１５は、コアの次数ｋに対する正規化エントロピーを示すグラフである。
ここでは複数コミュニティの抽出ができたk-dense法の４≦ｋ≦７とCFinderの３≦ｋ≦７で比較している。ｋ＝４で顕著な差が見られる。ただし、図１４に示すように、このときCFinderは千近い数の細分化されたコミュニティ群を抽出してしまっており、バランスに欠けるのに対し、k-dense法ではより安定した抽出結果となっている。
【００７６】
＜Wikipedia（登録商標）ネットワークでの評価＞
Wikipedia（登録商標）ネットワークに対して、本発明（k-dense法）、k-core法、および、k-clique法（CFinder）を適用した。結果、コミュニティが存在した最大次数はk-dense法では３６に、k-core法では４８となった。一方、ネットワーク規模が大きいためCFinderでは必要なメモリ量が爆発的に増加するため、結果が得られなかった。
【００７７】
以下では、k-core法とk-dense法との比較の詳細を述べる。
【００７８】
図１６、図１７および図１８は、各々、次数ｋに対するコミュニティ全体のサイズ、最大コミュニティのサイズおよびコミュニティ数を示すグラフである。
結果の傾向は、前記２種のネットワークへ各方法を適用した場合の結果と類似した。すなわち、図１６および図１７より、k-dense法と比較して、k-core法で抽出したコミュニティ全体と最大コミュニティのサイズとはかなり大きいことが分かる。なお、図１７の最大コミュニティのサイズに関して、k-dense法では、ｋ＝１２で３６-cliqueを抽出し、これがｋ＝３６まで最大コミュニティとなった。また、このネットワークでもk-core法での最大コミュニティのサイズは、コミュニティ全体のサイズに近く多くのノードが最大コミュニティに集中していることが分かる。
【００７９】
図１８に示すコミュニティ数の比較では、２３≦ｋ≦３１において、両手法が抽出したコミュニティ数が一致している。詳しく調べると、この範囲において、k-core法は、１，０００程度のノードを含む最大コミュニティとともに、２３≦ｋ≦３６のk-clique群を抽出していた。抽出されたk-clique例としては，“List of authors by name A”から、“List of authors by name Z”というようなノード群が完全結合しているネットワークであった。k-dense法でもこれらを抽出し、最大k-coreコミュニティが１つのk-denseコミュニティとなった範囲において、両手法で抽出したコミュニティ数が一致した。
【００８０】
図１９は、次数ｋに対する正規化エントロピーを表す。ｋ≧６では、k-denseは比較的均等なサイズのコミュニティ群を抽出している。これに対してk-core法では、全体的にかなり偏りが大きいことが分かる。
【００８１】
＜コミュニティ抽出例による評価＞
本発明（k-dense法）の有効性をさらに検証するために、k-core法およびk-clique法（CFinder）で抽出したコミュニティを可視化し、評価する。尚、可視化にはKamada-Kawaiばねモデルを用いた。
【００８２】
図２０は、ｋ＝６で単語連想ネットワークに本発明（k-dense法）とCFinderとを適用し、抽出されたコミュニティ例を示す可視化結果図である。
k-dense法は１つのコミュニティとして抽出したが、CFinderはノード重複を許容した３つのコミュニティとして抽出した。すなわち、CFinderによりオーバーラップするk-cliqueコミュニティが抽出できた例である。しかし、オーバーラップを直観的に理解するのに、図２０のような可視化がひとつの手段となり、k-cliqueコミュニティに細分化しなくても、k-denseコミュニティを抽出できれば十分な場合も少なくない。
【００８３】
図２１は、ｋ＝６で単語連想ネットワークにk-core法を適用し、抽出したコミュニティを示す可視化結果図である。
ただし、煩雑となるためリンクの表示は割愛している。明らかに、このようなk-coreコミュニティによるネットワークの構造分析には限界がある。
【００８４】
図２２は、人名共起ネットワークをKamada-Kawaiばねモデルを用いて可視化した可視化結果図である。
ここで人名共起ネットワークとは、Wikipedia（登録商標）（日本語版）の人名に関する記事（説明ページ）に着目し、これらの記事がWikipedia（登録商標）の記事全体からどのようにハイパーリンクによって参照されているか、すなわち、各人名記事のペアに対して、これら両方を参照する共通の記事（人名に限らず）がどれくらいあるか、という記事参照の共起関係に着目し、共起性の高さをフィッシャーの正確確率検定によって検定し、共起性の高いと判定された人名記事間にネットワークとしてのリンク（辺）を張る、という方法で抽出して生成したネットワークである。図２２は人名ネットワーク全体（ノード数１２９１３）をKamada-Kawaiばねモデルを用いて可視化した結果を示す。この図のように、単純にネットワーク全体を可視化するだけでは、ネットワークの構造的特徴は明らかにはならない。
【００８５】
一方、図２３は、この日本語版Wikipedia（登録商標）より抽出して生成した人名ネットワークに対しk-dense法を適用し、ｋ＝７のk-denseに属する人名のみのサブネットワークを可視化した可視化結果図である。
全体のネットワークを単純に可視化しただけでは判別困難であったネットワークの構造がより明確になっていることがわかる。
【００８６】
以上のように、本実施形態による方法、すなわちk-dense法は、k-core法に準じた高速性、k-clique法に迫る精度を持ち、その上k-core法、k-clique法のいずれに較べてより安定した抽出結果を生成する、優れたコア抽出アルゴリズムであって、本k-dense法を用いることによって、全体のネットワークから、ノードが密結合するコア部分とそれらの接続関係を抽出することで、ネットワーク全体の構造的特徴を明らかにすることができる。
【図面の簡単な説明】
【００８７】
【図１】k-coreコミュニティの一例を示す模式図である（比較例）。
【図２】k-cliqueコミュニティの一例を示す模式図である（比較例）。
【図３】k-denseコミュニティの一例を示す模式図である（本発明）。
【図４】本発明による一実施形態のネットワークコア抽出装置の構成を示すブロック図である。
【図５】k-dense抽出手順を示すフローチャートである。
【図６】小規模なネットワークに対しk-dense抽出を行った実行例を段階的に示す説明図である。
【図７】比較例であるk-core、k-coreと本発明によるk-denseの間の包含関係を示す図である。
【図８】本発明の抽出性能を比較例のものと比較した結果を示すための図である（ブログＴＢネットワークでのコミュニティ全体サイズの比較）。
【図９】本発明の抽出性能を比較例と比較した結果を示すグラフである（ブログＴＢネットワークでの最大コミュニティのサイズの比較）。
【図１０】本発明の抽出性能を比較例と比較した結果を示すグラフである（ブログＴＢネットワークでのコミュニティ数の比較）。
【図１１】本発明の抽出性能を比較例と比較した結果を示すグラフである（ブログＴＢネットワークでの正規化エントロピーの比較）。
【図１２】本発明の抽出性能を従来法と比較した結果を示すグラフである（単語連想ネットワークでのコミュニティ全体サイズの比較）。
【図１３】本発明の抽出性能を比較例と比較した結果を示すグラフである（単語連想ネットワークでの最大コミュニティのサイズの比較）。
【図１４】本発明の抽出性能を比較例と比較した結果を示すグラフである（単語連想ネットワークでのコミュニティ数の比較）。
【図１５】本発明の抽出性能を比較例と比較した結果を示すグラフである（単語連想ネットワークでの正規化エントロピーの比較）。
【図１６】本発明の抽出性能を比較例と比較した結果を示すグラフである（Wikipedia（登録商標）ネットワークでのコミュニティ全体サイズの比較）。
【図１７】本発明の抽出性能を比較例と比較した結果を示すグラフである（Wikipedia（登録商標）ネットワークでの最大コミュニティのサイズの比較）。
【図１８】本発明の抽出性能を比較例と比較した結果を示すグラフである（Wikipedia（登録商標）ネットワークでのコミュニティ数の比較）。
【図１９】本発明の抽出性能を比較例と比較した結果を示すグラフである（Wikipedia（登録商標）ネットワークでの正規化エントロピーの比較）。
【図２０】本発明の抽出性能をk-clique法（CFinder）と比較した結果を示すための可視化結果図である。
【図２１】k-core法での抽出結果を示すための図である。
【図２２】人名ネットワーク全体の可視化結果を示すための図である。
【図２３】人名ネットワークよりk-dense法で抽出したサブネットワークの構造を示すための図である。
【符号の説明】
【００８８】
１      入力部
２      共通隣接ノードカウント部
３      リンク削除処理部
４      ノード削除処理部
５      コア条件判定部
６      出力部
７      データ格納部
８      制御部
【図１】
0004714080.tif 000013
【図２】
0004714080.tif 000014
【図３】
0004714080.tif 000015
【図４】
0004714080.tif 000016
【図５】
0004714080.tif 000017
【図６】
0004714080.tif 000018
【図７】
0004714080.tif 000019
【図８】
0004714080.tif 000020
【図９】
0004714080.tif 000021
【図１０】
0004714080.tif 000022
【図１１】
0004714080.tif 000023
【図１２】
0004714080.tif 000024
【図１３】
0004714080.tif 000025
【図１４】
0004714080.tif 000026
【図１５】
0004714080.tif 000027
【図１６】
0004714080.tif 000028
【図１７】
0004714080.tif 000029
【図１８】
0004714080.tif 000030
【図１９】
0004714080.tif 000031
【図２０】
0004714080.tif 000032
【図２１】
0004714080.tif 000033
【図２２】
0004714080.tif 000034
【図２３】
0004714080.tif 000035