このトレンドは止められない！すべてのデータ サイエンティストが知っておくべき 5 つのグラフ アルゴリズム

すべてがつながっている世界では、ユーザーは独立した個人ではなく、何らかの形で互いにつながっています。機械学習モデルを構築する場合、この種の接続がモデルに組み込まれることがあります。

[[277932]]

リレーショナル データベースでは異なる行 (ユーザー) 間でこのような関係を使用することはできませんが、グラフ データベースでは非常に簡単に行うことができます。

この記事では、データ サイエンティストが知っておく必要がある重要なグラフ アルゴリズムをいくつか紹介し、それらを Python で使用する方法について説明します。

また、まずはグラフ理論の基礎を学ぶことを強くお勧めします。

サンディエゴ大学は、Coursera でビッグデータに関するグラフ分析コースを公開しました: https://www.coursera.org/learn/big-data-graph-analytics?ranMID=40328&ranEAID=lVarvwc5BD0&ranSiteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&siteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&utm_content=2&utm_medium=partners&utm_source=linkshare&utm_campaign=lVarvwc5BD0

1. 接続されたブランチ

3つの連結要素を持つグラフ

クラスタリング アルゴリズムがどのように機能するかは誰もが知っていますよね?

簡単に言えば、接続されたコンポーネントをハード クラスタリング アルゴリズムとして考え、関連する/接続されたデータ内のクラスター/アイランドを見つけるようにします。

具体的な例を見てみましょう。世界中の 2 つの都市を結ぶ道路データがあり、それを使用して世界中のすべての大陸とそこに含まれる都市を見つける必要があるとします。

どうすればこれを実現できるでしょうか? 頭を使ってください。

ここで使用される連結分岐アルゴリズムは BFS/DFS の特殊なケースであり、ここでは詳細には説明しません。以下では、Networkx を使用してコードを起動して実行する方法について説明します。

応用

小売業の観点から: 多くの顧客が多くの口座を持っていると仮定すると、接続された支店アルゴリズムを使用してデータセット内のさまざまな世帯を見つけることができます。

顧客ID間の接続（パス）は、同じクレジットカードの使用、同じ住所、同じ電話番号などに基づいて推定できます。これらの接続を確立したら、接続ブランチ アルゴリズムを実行して個別のクラスターを作成し、それに世帯 ID を割り当てることができます。

これらのファミリー ID は、家族のニーズに基づいてパーソナライズされた推奨事項を提供するために使用されます。また、ファミリーベースのグループ化機能を作成し、分類アルゴリズムを継続的に改善するためにも使用できます。

財務的な観点から: これらの家族 ID は詐欺を捕まえるためにも使用できます。 1 つのアカウントに詐欺の履歴がある場合、関連するアカウントでも詐欺が行われる可能性が高くなります。

可能性は無限であり、制限となるのはあなたの想像力だけです。

コーディング

Python の Networkx モジュールを使用してグラフを作成および分析します。

まず、都市間の距離情報が含まれる、使用されるグラフの例を見てみましょう。

ランダム距離図

まず、接続のリストと、接続の重みとして機能する距離のリストを作成します。

 edgelist = [[ 'マンハイム' 、 'フランクフルト' 、 85], [ 'マンハイム' 、 'カールスルーエ' 、 80], [ 'エアフルト' 、 'ヴュルツブルク' 、 186], [ 'ミュンヘン' 、 'ナンバリング' 、 167], [ 'ミュンヘン' 、 'アウクスブルク' 、 84], [ 'ミュンヘン' 、 'カッセル' 、 502], [ 'ナンバリング' 、 'シュトゥットガルト' 、 183], [ 'ナンバリング' 、 'ヴュルツブルク' 、 103], [ 'ナンバリング' 、 'ミュンヘン' 、 167], [ 'シュトゥットガルト' 、 'ナンバリング' 、 183] 'アウクスブルク' 、 'ミュンヘン' 、 84]、[ 'アウクスブルク' 、 'カールスルーエ' 、 250]、[ 'カッセル' 、 'ミュンヘン' 、 502]、[ 'カッセル' 、 'フランクフルト' 、 173]、[ 'フランクフルト' 、 'マンハイム' 、 85]、[ 'フランクフルト' 、 'ヴュルツブルク' 、 217]、[ 'フランクフルト' 、 'カッセル' 、 173]、[ 'ヴュルツブルク' 、 'ナンベルグ' 、 103]、[ 'ヴュルツブルク' 、 'エアフルト' 、 186]、[ 'ヴュルツブルク' 、 'フランクフルト' 、 217]、[ 「カールスルーエ」 、 「マンハイム」 、「80」]、[ 「カールスルーエ」 、 「アウクスブルク」 、「250」]、[ 「ムンバイ」 、 「デリー」 、「400」]、[ 「デリー」 、 「コルカタ」 、「500」]、[ 「コルカタ」 、 「バンガロール」 、「600」]、[ 「TX」 、 「NY」 、「1200」]、[ 「ALB」 、 「NY」 、「800」]]

Networkx を使用してグラフを作成します。

 g = nx.グラフ()
 edgelist内のedgeの場合:
 g.add_edge(エッジ[0]、エッジ[1]、重み = エッジ[2])

次に、この地図からさまざまな大陸とその都市を見つける必要があります。

接続コンポーネントアルゴリズムは次のように使用できます。

 i, xがenumerate(nx.connected_components(g))に含まれる場合:
 print( "cc" +str(i)+ ":" ,x)
 ------------------------------------------------------------  
 cc0: { 'フランクフルト' 、 'カッセル' 、 'ミュンヘン' 、 'ナンベルク' 、 'エアフルト' 、 'シュトゥットガルト' 、 'カールスルーエ' 、 'ヴュルツブルク' 、 'マンハイム' 、 'アウグスブルク' }
 cc1: { 'コルカタ' 、 'バンガロール' 、 'ムンバイ' 、 'デリー' }
 cc2: { 'ALB' 、 'NY' 、 'TX' }

上記のように、接続と頂点のみを使用してデータ内のさまざまなコンポーネントを見つけることができます。このアルゴリズムは、上記のいずれかのケースを満たすために、さまざまなデータに対して実行できます。

2. 最短経路

上記はドイツの都市とそれらの間の距離を示しています。

次に、フランクフルト（出発地）からミュンヘンまでの最短距離を見つける必要があります。

この問題を解決するアルゴリズムはダイクストラのアルゴリズムと呼ばれます。ダイクストラ自身の言葉によれば、

ロッテルダムからフローニンゲンへ行く最も早い方法は何ですか？ あるいは、どの都市からどの都市へ行くのにも同じです。この最短経路アルゴリズムを設計するのにたった 20 分しかかかりませんでした。ある朝、私は若い婚約者とアムステルダムで買い物をしていました。歩き疲れたので、カフェのテラスに座ってコーヒーを飲みながら、「私にもできるかな？」と思い、最短経路アルゴリズムを設計しました。前にも述べたように、これは 20 分間の発明です。実際、この本は3年後の1959年に出版され、今でも読むことができます。鉛筆と紙でデザインしなかったからこそ、良い本になったのです。後に、鉛筆と紙を使わずにデザインする利点の 1 つは、物事をシンプルに保てることだということに気付きました。結局、このアルゴリズムが私の最高傑作の 1 つになるとは思っていませんでした。

— エドガー・ダイクストラ、フィリップ・L・フラナとのインタビュー、Communications of the ACM、2001[3]

応用

• ダイクストラのアルゴリズムの進化版は、最短経路を見つけるために Google マップで広く使用されています。
• あなたがウォルマートで働いているとします。さまざまな通路とすべての通路間の距離がわかっているので、顧客がいる通路 A から通路 D までの最短経路を見つけます。

• LinkedIn には、第 1 レベルおよび第 2 レベルのつながりが多数あります。これらの接続はどのように機能するのでしょうか?

コーディング

print(nx.shortest_path(g, 'シュトゥットガルト' , 'フランクフルト' ,weight= 'weight' ))
 print(nx.shortest_path_length(g, 'シュトゥットガルト' , 'フランクフルト' ,weight= 'weight' ))
 --------------------------------------------------------  
 [ 'シュトゥットガルト' 、 'ナンベルク' 、 'ヴュルツブルク' 、 'フランクフルト' ]
 503

次のコマンドを使用して、すべての都市ペア間の最短経路を見つけることもできます。

 nx.all_pairs_dijkstra_path(g,weight= 'weight' )内のxについて:
 印刷(x)
 --------------------------------------------------------  
 ( 'マンハイム' 、 { 'マンハイム' : [ 'マンハイム' ], 'フランクフルト' : [ 'マンハイム' 、 'フランクフルト' ], 'カールスルーエ' : [ 'マンハイム' 、 'カールスルーエ' ], 'アウクスブルク' : [ 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' ], 'カッセル' : [ 'マンハイム' 、 'フランクフルト' 、 'カッセル' ], 'ヴュルツブルク' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' ], 'ミュンヘン' : [ 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' 、 'ミュンヘン' ], 'エアフルト' ] } ) ( 'フランクフルト ' 、 { 'フランクフルト' : [ 'フランクフルト' ]、 'マンハイム' : [ 'フランクフルト ' 、 'マンハイム' ] 、 'カッセル' : [ 'フランクフルト' 、 'カッセル' ] 、 'ヴュルツブルク' : [ 'フランクフルト' 、 'マンハイム' ] ], 'ミュンヘン' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' 、 'ミュンヘン' ] 、 'エアフルト' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'エアフルト' ] 、 'ナンベルク' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' ] 、 'シュトゥットガルト' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' ] 「Numberg」 、 「シュトゥットガルト」 ]})。

3. 最小全域木 (MST)

ここで別の問題が発生します。あなたが水道管敷設会社またはインターネット光ファイバー会社で働いていて、グラフ内のすべての都市を最小限の電線/パイプで接続する必要がある場合、どのようにしますか?

MSTが右側にある無向グラフ

応用

• MST はネットワーク設計に直接適用されます。これらには、コンピュータ ネットワーク、通信ネットワーク、輸送ネットワーク、給水ネットワーク、電力網 (元々この目的のために設計された) が含まれます。
• MSTは巡回セールスマン問題の解決にも使われる
• クラスタリング - まずMSTを構築し、次にクラスタ間距離とクラスタ内距離を使用して閾値を決定し、それによってMST内のいくつかの同点を解消します。
• 画像セグメンテーション – まず、ピクセルがノードとなり、ピクセル間の距離が何らかの類似性尺度（色、強度など）に基づいているグラフに MST を構築します。

コーディング

# nx.minimum_spanning_tree(g) はグラフ型のインスタンスを返します
nx.draw_networkx(nx.minimum_spanning_tree(g))

この図のMST

上の写真のように配線を敷設する必要があります。

4. ページランク

上の画像は、Google の Web ページランキング アルゴリズムです。着信接続と発信接続の数と品質に基づいてページにスコアを割り当てます。

応用

Page Rank は、ネットワーク ノードの重要性を推定する必要があるあらゆる場所で使用できます。

• 引用文献を使用して最も影響力のある論文を見つけるために使用
• Googleでページのランク付けに使用
• ユーザーとツイートをノードとして、ツイートを並べ替えるのにも使用できます。ユーザー A がユーザー B をフォローすると、ユーザー間の接続が作成されます。ユーザーがツイートを送信またはリツイートすると、ユーザーとツイートの間に接続が作成されます。
• 推奨エンジン

コーディング

この演習では Facebook データを使用します。こちらはFacebookユーザー間の接続/リンクファイルです。まず、次のように Facebook グラフを作成します。

 # データセットの読み取りfb = nx.read_edgelist( '../input/facebook-combined.txt' , create_using = nx.Graph(), nodetype = int )

仕組みは次のとおりです:

 pos = nx.spring_layout(fb) インポートの警告
warnings.filterwarnings( '無視' )plt.style.use( 'fivethirtyeight' )
 plt.rcParams[ 'figure.figsize' ] = (20, 15)
 plt.axis( 'オフ' )
 nx.draw_networkx(fb, pos, with_labels = False 、node_size = 35) を描画します。
 plt.show()

FB ユーザーグラフ

次に、影響力の高いユーザーを見つける必要があります。

直感的に言えば、ページランキングアルゴリズムは多くの友達を持つユーザーに高いスコアを与え、これらのユーザーは Facebook 上に多くの友達を持っています。

ページランク = nx.pagerank(fb)
印刷(ページランク)
 ------------------------------------------------------  
 {0: 0.006289602618466542,
 1: 0.00023590202311540972,
 2: 0.00020310565091694562,
 3: 0.00022552359869430617,
 4: 0.00023849264701222462,
 ........}

これにより、Web ページのランキング アルゴリズムまたは最も影響力のあるユーザーの並べ替えられたリストが表示されます。

インポート演算子
sorted_pa​​gerank = sorted(pagerank.items(), key = operator.itemgetter(1), reverse = True ) です。
印刷(ソートされたページランク)
 ------------------------------------------------------  
 [(3437, 0.007614586844749603), (107, 0.006936420955866114), (1684, 0.0063671621383068295), (0, 0.006289602618466542), (1912, 0.0038769716008844974), (348, 0.0023480969727805783), (686, 0.0022193592598000193), (3980, 0.002170323579009993), (414, 0.0018002990470702262)、(698、0.0013171153138368807)、(483、0.0012974283300616082)、(3830、0.0011844348977671688)、(376、0.0009014073664792464)、(2047、0.000841029154597401)、(56、0.0008039024292749443)、(25、0.000800412660519768)、(828、0.0007886905420662135)、 （322、0.0007867992190291396）、......]

上記の ID は最も影響力のあるユーザーに使用されます。

ここでは影響力のあるユーザーのサブグラフを見ることができます。

 1次接続ノード = list(fb.neighbors(3437))
 2次接続ノード数 = []
 first_degree_connected_nodes内のxの場合:
 2次接続ノード+=list(fb.neighbors(x))
 2番目の接続ノードを削除します(3437)
 second_degree_connected_nodes = list( set (second_degree_connected_nodes))subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes)pos = nx.spring_layout(subgraph_3437)node_color = [ 'yellow' if v == 3437 else   '赤'  サブグラフ_3437のvについて]
 node_size = [v == 3437 の場合は 1000 、それ以外の場合はsubgraph_3437内のvの場合は35 ]
 plt.style.use( 'fivethirtyeight' )
 plt.rcParams[ 'figure.figsize' ] = (20, 15)
 plt.axis( 'off' )nx.draw_networkx(subgraph_3437, pos, with_labels = False , node_color = node_color, node_size = node_size)
 plt.show()

最も影響力のあるユーザー（黄色の点）

5. 中心性指標

中心性指標には、機械学習モデルで使用できる多くの特性があります。そのうちの2つを以下に紹介します。他の測定方法については、こちらをご覧ください: https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html

媒介中心性: 最も多くの友人を持つユーザーは重要であり、2 つの地理的な場所のユーザーを接続することも重要です。これにより、ユーザーは異なる地理的な場所からのコンテンツを表示できるようになります。媒介中心性は、特定のノードが他の 2 つのノード間の最短経路に出現する回数を定量化します。

次数中心性: ノードが持つ接続の数。

応用

中心性指標は、あらゆる機械学習モデルの機能として使用できます。

コーディング

次のコードは、サブグラフの媒介中心性を見つけるために使用されます。

位置 = nx.spring_layout(サブグラフ_3437)
 betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized= True , endpoints= True )node_size = [v * 10000 for v in betweennessCentrality.values () ]
 plt.figure(図サイズ=(20,20))
 nx.draw_networkx(subgraph_3437, pos=pos, with_labels= False ,
 ノードサイズ=ノードサイズ)
 plt.axis( 'オフ' )

上記のように、ノードのサイズは媒介中心性の値に応じて調整されます。これらのノードは情報送信機とみなすことができます。媒介中心性が高いノードを切断すると、グラフは多くの部分に分割されます。

要約する

この記事では、さまざまな面で人々のライフスタイルを変えた非常に影響力のあるグラフアルゴリズムをいくつか紹介します。

大量のソーシャル データの出現により、ネットワーク分析はモデルの改善、大きな価値の創出、さらには世界に対する人間の理解の向上に大きく役立ちます。

最近は多くのグラフ アルゴリズムが登場していますが、上記のものは私のお気に入りです。ご興味がございましたら、ぜひこれらのアルゴリズムについて深く研究してみてください。この記事では、この分野について限定的に紹介するのみです。

この記事で言及されているすべてのアルゴリズムの Kaggle カーネルはこちらです: https://www.kaggle.com/mlwhiz/top-graph-algorithms