特許ウォッチ

公開番号2024102012
公報種別公開特許公報(A)
公開日2024-07-30
出願番号2024004725
出願日2024-01-16
発明の名称組み合わせの最適化公式を用いたグラフデータセット内のインフルエンシャルノードの特定
出願人富士通株式会社
代理人個人,個人
主分類G06F 16/906 20190101AFI20240723BHJP(計算;計数)
要約【課題】本開示は、グラフデータセット内のインフルエンシャルノードの特定する方法を提供する。
【解決手段】方法は、ソーシャルネットワークを表した、複数のノードを含むグラフデータセットを取得することを含み得る。当該方法は、グラフデータセットを第1のノードクラスタ及び第2のノードクラスタに分割することを含むことができ、第1のノードクラスタ及び第2のノードクラスタは各々、グラフデータセットからの1つ以上のノードを含む。当該方法は、第1のノードクラスタに含まれる1つ以上の第1の候補インフルエンシャルノード、及び第2のノードクラスタに含まれる1つ以上の第2の候補インフルエンシャルノードを特定することを含み得る。当該方法は、第1の候補インフルエンシャルノード及び第2の候補インフルエンシャルノードのうちの1つ以上をインフルエンサノードとして選択し、インフルエンサノードの各々に対応するソーシャルネットワークに含まれるそれぞれのオブジェクトを特定することを含み得る。
【選択図】図3
特許請求の範囲【請求項１】
複数のノードを含むグラフデータセットを取得し、該グラフデータセットはソーシャルネットワークを表し、
前記グラフデータセットを第１のノードクラスタ及び第２のノードクラスタに分割し、該第１のノードクラスタ及び該第２のノードクラスタは各々、前記グラフデータセットからの１つ以上のノードを含み、
前記第１のノードクラスタに含まれる１つ以上の第１の候補インフルエンシャルノード、及び前記第２のノードクラスタに含まれる１つ以上の第２の候補インフルエンシャルノードを特定し、
前記第１の候補インフルエンシャルノード及び前記第２の候補インフルエンシャルノードのうちの１つ以上をインフルエンサノードとして選択し、
前記インフルエンサノードの各々に対応する前記ソーシャルネットワークに含まれるそれぞれのオブジェクトを特定する、
ことを有する方法。
続きを表示（約 2,100 文字）【請求項２】
前記グラフデータセットを前記第１のノードクラスタ及び前記第２のノードクラスタに分割することは、前記第１のノードクラスタ及び前記第２のノードクラスタが同じ数のノード又は互いの閾値内の数のノードを含むように前記グラフデータセットを分けることを含む、請求項１に記載の方法。
【請求項３】
前記第１のノードクラスタに含まれるとして特定される第１の候補インフルエンシャルノードの数、及び前記第２のノードクラスタに含まれるとして特定される第２の候補インフルエンシャルノードの数は、前記グラフデータセットに含まれるノードの総数に比例する、請求項１に記載の方法。
【請求項４】
前記インフルエンサノードを選択することは、
前記第１の候補インフルエンシャルノード及び前記第２の候補インフルエンシャルノードを一組の候補インフルエンシャルノードとして集約し、
前記一組の候補インフルエンシャルノードに含まれる各ノードの、前記グラフデータセットに含まれる他のノード各々に対するそれぞれの影響力を合計することに基づいて、前記一組の候補インフルエンシャルノードの累積影響力を決定する、
ことを含み、
前記インフルエンサノードは、前記グラフデータセットに含まれる他のノードに及ぼされる前記第１の候補インフルエンシャルノード及び前記第２の候補インフルエンシャルノードのそれぞれの影響力に基づいて、前記一組の候補インフルエンシャルノードから選択される、
請求項１に記載の方法。
【請求項５】
前記グラフデータセットは、前記複数のノードを接続するエッジがそれぞれの重み値及びそれぞれの方向性を含んだ、重み付き有向グラフデータセットである、請求項１に記載の方法。
【請求項６】
前記第１の候補インフルエンシャルノードの各々と前記第２の候補インフルエンシャルノードの各々の影響力の程度を決定することは、特定の第１の候補インフルエンシャルノード又は特定の第２の候補インフルエンシャルノードから生じて前記グラフデータセットに含まれる他のノードに接続するエッジの累積和を計算することを含む、請求項５に記載の方法。
【請求項７】
それぞれのインフルエンサノードに対応するとして特定される前記ソーシャルネットワークに含まれる前記オブジェクトは、前記ソーシャルネットワーク上でのユーザアカウントである、請求項１に記載の方法。
【請求項８】
命令を格納するように構成された１つ以上の非一時的コンピュータ読み取り可能記憶媒体であって、前記命令は、実行されることに応答して、システムに処理を実行させ、該処理は、
複数のノードを含むグラフデータセットを取得し、該グラフデータセットはソーシャルネットワークを表し、
前記グラフデータセットを第１のノードクラスタ及び第２のノードクラスタに分割し、該第１のノードクラスタ及び該第２のノードクラスタは各々、前記グラフデータセットからの１つ以上のノードを含み、
前記第１のノードクラスタに含まれる１つ以上の第１の候補インフルエンシャルノード、及び前記第２のノードクラスタに含まれる１つ以上の第２の候補インフルエンシャルノードを特定し、
前記第１の候補インフルエンシャルノード及び前記第２の候補インフルエンシャルノードのうちの１つ以上をインフルエンサノードとして選択し、
前記インフルエンサノードの各々に対応する前記ソーシャルネットワークに含まれるそれぞれのオブジェクトを特定する、
ことを有する、１つ以上の非一時的コンピュータ読み取り可能記憶媒体。
【請求項９】
システムであって、
１つ以上のプロセッサと、
命令を格納するように構成された１つ以上の非一時的コンピュータ読み取り可能記憶媒体と、
を有し、
前記命令は、実行されることに応答して、当該システムに処理を実行させ、該処理は、
複数のノードを含むグラフデータセットを取得し、該グラフデータセットはソーシャルネットワークを表し、
前記グラフデータセットを第１のノードクラスタ及び第２のノードクラスタに分割し、該第１のノードクラスタ及び該第２のノードクラスタは各々、前記グラフデータセットからの１つ以上のノードを含み、
前記第１のノードクラスタに含まれる１つ以上の第１の候補インフルエンシャルノード、及び前記第２のノードクラスタに含まれる１つ以上の第２の候補インフルエンシャルノードを特定し、
前記第１の候補インフルエンシャルノード及び前記第２の候補インフルエンシャルノードのうちの１つ以上をインフルエンサノードとして選択し、
前記インフルエンサノードの各々に対応する前記ソーシャルネットワークに含まれるそれぞれのオブジェクトを特定する、
ことを有する、
システム。

発明の詳細な説明【技術分野】
【０００１】
本開示は概して、組み合わせの最適化公式を用いたグラフデータセット内の影響力あるノード（インフルエンシャルノード）の特定に関する。
続きを表示（約 3,300 文字）【背景技術】
【０００２】
グラフと称されるデータセットに含まれる複数のノードとしてデータポイントが表現されることがある。グラフデータセットに含まれるノードは、ノード間の類似性及び差異に従って、共にグループ化され得る。所与のデータ分析タスク又は目標に従ってノードを１つ以上のグループに分類するために機械学習モデルが訓練され得る。
【０００３】
本開示にて特許請求される事項は、上述のような環境でのみ問題を解決したり動作したりする実施形態に限定されるものではない。むしろ、この背景技術の説明は、本開示にて記載される実施形態が実施され得る技術領域の一例を示すために提供されているに過ぎないものである。
【発明の概要】
【０００４】
一実施形態の一態様によれば、方法は、ソーシャルネットワークを表した、複数のノードを含むグラフデータセットを取得することを含み得る。当該方法は、グラフデータセットを第１のノードクラスタ及び第２のノードクラスタに分割することを含むことができ、第１のノードクラスタ及び第２のノードクラスタは各々、グラフデータセットからの１つ以上のノードを含む。当該方法は、第１のノードクラスタに含まれる１つ以上の第１の候補インフルエンシャルノード、及び第２のノードクラスタに含まれる１つ以上の第２の候補インフルエンシャルノードを特定することを含み得る。当該方法は、第１の候補インフルエンシャルノード及び第２の候補インフルエンシャルノードのうちの１つ以上をインフルエンサノードとして選択し、インフルエンサノードの各々に対応するソーシャルネットワークに含まれるそれぞれのオブジェクトを特定することを含み得る。
【０００５】
実施形態の目的及び利点は、少なくとも請求項中に具体的に指し示される要素、機構及び組み合わせによって実現・達成されることになる。理解されるべきことには、以上の概略説明及び以下の詳細説明はどちらも、例として与えられ、説明的なものであり、特許請求される発明を限定するものではない。
【図面の簡単な説明】
【０００６】
以下の図を含む添付図面を通じて実施形態例を更に具体的且つ詳細に記載・説明する。
本開示の１つ以上の実施形態に従った、グラフデータセットに含まれるインフルエンシャルノードが特定され得る動作環境例の図である。
本開示の１つ以上の実施形態に従って特定可能なインフルエンシャルノードを含み得る例示的なグラフデータセット例を示している。
本開示の１つ以上の実施形態に従った、グラフデータセットに含まれるインフルエンシャルノードを特定する方法例のフローチャートである。
本開示の１つ以上の実施形態に従ったコンピュータシステム例である。
【発明を実施するための形態】
【０００７】
オブジェクトのセットを、そのセットに含まれるオブジェクトが何らかの形で互いに関係している場合に、相互に関係するネットワークの一部であると見なすことができる。例えば、ある特定のセットのオブジェクトは、ソーシャルメディアプラットフォーム上のユーザアカウントのグループを含むことができ、ある特定のユーザアカウントが、ユーザアカウント間の友人関係、フォロー・フォロワー関係、社会的交流、又はユーザアカウント間の任意の他のタイプの関係を介して、１つ以上の他のユーザアカウントと関係していることがある。追加の又は代替的な例として、ある特定のセットのオブジェクトは、特定の地理的エリア内の１つ以上の位置を含むことができ、それらの位置間の関係は、特定の地理的エリア内で特定の位置を１つ以上の他の位置に接続する道路を含む。相互に関係するオブジェクトは、それらのオブジェクトのうちの２つ以上の間の関係のために分析するのが困難であることがある。さらに、オブジェクトの数が増加するにつれて、オブジェクト間の関係の複雑さも増加することがあり、それが分析の難しさを更に高め得る。グラフデータセットは、そのような相互に関係するオブジェクトを、オブジェクトのネットワークとして定量化及びモデル化するのに使用されることができ、ネットワークに含まれるオブジェクトのペアは、互いに関係していることもあれば関係していないこともある。特定のグラフデータセットは、特定のネットワーク内のオブジェクトを表す頂点と、特定のグラフデータセットに含まれる２つのオブジェクトを接続するエッジとを含み得る。一部の状況において、エッジは、特定のオブジェクト間の関係の方向性及び／又は重要性に関する定量的な情報を提供する有向エッジ及び／又は重み付きエッジであることができる。
【０００８】
相互に関係するオブジェクトをグラフデータセットとして表現することは、グラフデータセットに含まれる他のオブジェクトに何らかの形で影響を及ぼすグラフデータセットに含まれるノードとして特定される特定のオブジェクトの特定を容易にし得る。特定のオブジェクトが別のオブジェクトに影響を及ぼす形は、該特定のオブジェクトと該他のオブジェクトが関係するコンテキストに応じて、これらのオブジェクトが含まれる特定のネットワーク環境に応じて、又は任意の他の要因に基づいて、異なり得る。例えば、ソーシャルネットワークを表すグラフは、ユーザ、メディア、又は該ソーシャルネットワークに関係する任意の他のオブジェクトを表すノードを含むことができ、オブジェクトを接続するエッジは、友人関係、ページビュー、コメントする挙動、反応、印象、又はオブジェクト間の任意の他の相互関係を表すことができる。特定のオブジェクトがソーシャルネットワーク内の他のオブジェクトに対して持ち得る影響力は、特定のオブジェクトがどのように接続されているか（例えば、ソーシャルメディアインフルエンサアカウント）、特定のオブジェクトがどれだけ早く閲覧されたりその他の形で他のオブジェクトと交流したりするか（例えば、口コミ動画又はニュース記事）、又はこれらに類するものを含み得る。
【０００９】
既存の影響力モデルは、独立カスケード拡散モデルであり、これは、グラフに含まれるノードのうちのサブセットが、グラフ内の他のノードに対して、そのサブセットに含まれるノードとグラフ内のそれら他のノードとの間での特定のそれぞれの確率で影響を伝播し始めると仮定するものである。漸進的な時間ステップの各々において、影響を受けたノードは各々、１つ以上の隣接ノードに影響を与えて影響の伝播を続ける単一の機会を持つことができる。グラフに含まれるノードの全てが影響を受けるまで、新たに影響を受けたノードが他のノードに影響を伝播し続けることがある。グラフのノード間で影響がどのように伝播されたかに基づいて、特定のノードの影響力の程度が決定され得る。
【００１０】
加えて、あるいは代わりに、別の既存の影響力モデルは線形閾値拡散モデルである。線形閾値拡散モデルでは、各ノードにランダムな閾値パラメータを割り当てることができ、ノード間の各エッジにそれぞれの重みを関連付けることができる。特定のノードについて、該特定のノードによって影響を受けている隣接ノードのセットが、それらのノードの各々に割り当てられたランダムな閾値パラメータと、該特定のノードをその隣接ノードに接続するエッジの重みとに基づいて決定され得る。特定のノードがその隣接ノードに対してより大きな影響を及ぼすか、又はその隣接ノードによってより大きな影響を受けるかを決定する際に、異なる基準が考慮されてもよい。例えば、隣接ノードから特定のノードへのエッジの重みの第１の合計が、特定のノードから隣接ノードへのエッジの重みの第２の合計よりも大きい場合、特定のノードは影響を受けていると見なされ得る。
（【００１１】以降は省略されています）

関連特許