SNS分析

SNS上で、あるユーザーが自分の友達の友達の中で最も人気がある人を見つけるために、ネットワーク分析を行いたいと考えています。

この問題を解決するために、与えられたSNSグラフ内で、指定されたユーザーの友達の友達の中で最も人気がある人を見つける関数を実装してください。

解法

以下は、この問題に対するNetworkXによる実装例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import networkx as nx

def find_most_popular_friend_of_friends(G, user):
    """
    指定されたユーザーの友達の友達の中で最も人気がある人を見つける関数

    Parameters
    ----------
    G : NetworkXのグラフオブジェクト
        SNSグラフ
    user : ノード
        検索対象のユーザー

    Returns
    -------
    ノード
        最も人気があるユーザー
    """
    # userの友達を取得
    friends = set(nx.neighbors(G, user))

    # userの友達の友達を取得
    friends_of_friends = set()
    for friend in friends:
        friends_of_friends.update(nx.neighbors(G, friend))

    # userとその友達の友達を除く
    friends_of_friends.discard(user)
    friends_of_friends.difference_update(friends)

    # 各ノードの次数を計算
    degrees = G.degree(friends_of_friends)

    # 次数の降順にソート
    sorted_degrees = sorted(degrees, key=lambda x: x[1], reverse=True)

    # 最も人気のあるユーザーを返す
    return sorted_degrees[0][0]

この関数は、与えられたSNSグラフ内で指定されたユーザーの友達の友達の中で最も人気がある人を見つけるために使用できます。

与えられたユーザーの友達の友達を取得し、各ノードの次数を計算して、次数が最大のノードを返します。

動作確認

テスト用のデータを作成して、上記の関数を使用して解決してみましょう。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import networkx as nx

# SNSグラフを作成
G = nx.Graph()
G.add_edges_from([
    ('Alice', 'Bob'),
    ('Alice', 'Charlie'),
    ('Bob', 'David'),
    ('Bob', 'Eve'),
    ('Charlie', 'David'),
    ('Charlie', 'Frank'),
    ('David', 'Eve'),
    ('Eve', 'Frank'),
    ('Eve', 'Grace'),
    ('Frank', 'Grace')
])

# 'Alice'の友達の友達で最も人気がある人を見つける
most_popular_friend_of_friends = find_most_popular_friend_of_friends(G, 'Alice')

print(f"Most popular friend of friends of Alice: {most_popular_friend_of_friends}")

このコードでは、GというSNSグラフを作成し、find_most_popular_friend_of_friends関数を使用して、’Alice’の友達の友達で最も人気がある人を見つけています。

出力結果は以下の通りになります。

[実行結果]

Most popular friend of friends of Alice: Grace

与えられたSNSグラフ内で指定されたユーザーの友達の友達の中で最も人気がある人を見つけることができました。

強連結グラフ

強連結グラフとは、グラフ上の任意の2つの頂点間に有向パスが存在するグラフのことです。

強連結グラフの判定には、コサラージュのアルゴリズムが使用されます。

1. 与えられたグラフGに対して、グラフGの転置グラフGTを作成する。
2. Gの任意の頂点vからDFSを行い、訪れた頂点をスタックに追加する。
3. スタックの頂点を逆順にした順序で、GTに対してDFSを行い、訪れた頂点の集合を得る。
4. スタックに残っている頂点がある場合、その頂点からDFSを再開し、訪問順を追加していく。
5. 2-4を繰り返し、スタックが空になった場合、グラフGが強連結グラフであることが示される。

以下は、上記のアルゴリズムをPythonコードで実装した例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import networkx as nx

# グラフの作成
G = nx.DiGraph()
G.add_nodes_from([1, 2, 3, 4])
G.add_edges_from([(1, 2), (2, 3), (3, 1), (3, 4)])

# 転置グラフの作成
GT = G.reverse(copy=True)

# DFSを行い、スタックに追加
stack = []
visited = set()
for v in G.nodes:
    if v not in visited:
        visited.add(v)
        stack.append(v)
        while stack:
            node = stack[-1]
            neighbors = list(G.neighbors(node))
            unvisited = [n for n in neighbors if n not in visited]
            if unvisited:
                n = unvisited[0]
                visited.add(n)
                stack.append(n)
            else:
                stack.pop()

# スタックから頂点を逆順にして、転置グラフに対してDFSを行う
visited = set()
while stack:
    node = stack.pop()
    if node not in visited:
        visited.add(node)
        t_neighbors = list(GT.neighbors(node))
        for n in t_neighbors:
            if n not in visited:
                stack.append(n)

if len(visited) == len(G.nodes):
    print("グラフは強連結グラフです")
else:
    print("グラフは強連結グラフではありません")

上記のコードは、与えられたグラフが強連結グラフである場合、”グラフは強連結グラフです”と出力します。

強連結グラフが強連結グラフでない場合、”グラフは強連結グラフではありません”と出力されます。

このアルゴリズムは、与えられたグラフGに対して、転置グラフGTを作成し、GとGTのDFSを行うことで、強連結グラフであるかどうかを判断します。

GとGTのDFSを行うことで、G上の任意の2つの頂点間に有向パスが存在することを確認することができます。

そして、Gが強連結グラフであるためには、GとGTのDFSによって訪れた頂点が全て同一である必要があります。

このアルゴリズムは、時間計算量がO(V+E)であり、高速に強連結グラフかどうかを判断できます。

グラフ理論では、強連結グラフは重要な役割を持っており、多くのアルゴリズムに応用されます。

強連結グラフの判定アルゴリズムを理解することで、グラフ理論の基礎的な概念を深く理解することができます。

最大流問題

最大流問題は、与えられたグラフにおいて、ある2つの頂点を指定して、それらの間に最大量の流れを流す問題です。

以下は、NetworkXを使用して最大流問題を解く例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import networkx as nx

# グラフを作成
G = nx.DiGraph()

G.add_nodes_from(['S', 'A', 'B', 'C', 'D', 'T'])

G.add_edges_from([('S', 'A', {'capacity': 10}),
                  ('S', 'C', {'capacity': 5}),
                  ('A', 'B', {'capacity': 9}),
                  ('A', 'D', {'capacity': 4}),
                  ('B', 'T', {'capacity': 8}),
                  ('C', 'D', {'capacity': 3}),
                  ('C', 'T', {'capacity': 7}),
                  ('D', 'B', {'capacity': 6}),
                  ('D', 'T', {'capacity': 9})])

# 最大流を求める
max_flow_value, flow_dict = nx.maximum_flow(G, 'S', 'T', capacity='capacity')

# 結果を表示する
print('Maximum Flow Value:', max_flow_value)
print('Flow Dictionary:', flow_dict)

上記の例では、6つの頂点を持つグラフが与えられています。

SとTはそれぞれ始点と終点を表し、他の頂点は中間点として機能します。

各辺は容量を持ち、それが最大流を制限するものです。

maximum_flow関数は、グラフ、始点、終点、容量属性を受け取り、最大流量とフローの辞書を返します。

capacity引数は、各辺の容量を指定する属性名を表します。

実行結果は以下のようになります。

[実行結果]

Maximum Flow Value: 15
Flow Dictionary: {'S': {'A': 10, 'C': 5}, 'A': {'B': 8, 'D': 2}, 'B': {'T': 8}, 'C': {'D': 0, 'T': 5}, 'D': {'B': 0, 'T': 2}, 'T': {}}

この結果により、グラフの始点から終点に15の最大流量が流れることがわかります。

また、各辺のフローも辞書として表示されます。

ループ検出

ループ検出の例題として、以下のような有向グラフを考えてみましょう。

A -> B -> C -> D -> E

このグラフにはループが含まれていません。

しかし、次のようなグラフを考えてみましょう。

A -> B -> C -> D -> E -> A

このグラフには、ノードAからノードEに至るループが含まれています。

このグラフでループを検出するには、NetworkXのsimple_cycles関数を使用することができます。

以下は、コード例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import networkx as nx

# グラフを作成する
G = nx.DiGraph()
nodes = "ABCDE"
for i in range(len(nodes)):
    G.add_node(nodes[i])
    if i < len(nodes) - 1:
        G.add_edge(nodes[i], nodes[i+1])
G.add_edge(nodes[-1], nodes[0])

# ループを検出する
loops = list(nx.simple_cycles(G))
if len(loops) > 0:
    print("ループを検出しました:")
    print(loops)
else:
    print("ループは検出されませんでした。")

出力結果は以下のようになります。

[実行結果]

ループを検出しました:
[['D', 'E', 'A', 'B', 'C']]

このように、simple_cycles関数を使用することで、グラフ上のループを検出することができます。

次数

グラフ理論において、頂点の次数とは、その頂点に接続された辺の本数のことを指します。

グラフ理論では、次数は頂点の重要な特徴量の1つであり、グラフの性質を表すために用いられます。

例えば、無向グラフにおいて全ての頂点の次数が偶数である場合、オイラー路と呼ばれる全ての辺を1度だけ通るパスが存在することが知られています。

問題

以下のグラフの各頂点の次数を求めて下さい。

   1---2---3
      /    |
     /     |
   4-------5

ソースコード

以下のようにPythonコードを書くことができます。

1
2
3
4
5
6
7
8
9

import networkx as nx

# グラフを作成する
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5), (5, 3)])

# 各頂点の次数を計算する
degrees = dict(G.degree())
print(degrees)

実行すると、以下のような出力が得られます。

[実行結果]

{1: 1, 2: 3, 3: 2, 4: 2, 5: 2}

これは、頂点1の次数が1、頂点2の次数が3、頂点3の次数が2、頂点4の次数が2、頂点5の次数が2であることを示しています。

クラスタリング問題

クラスタリング問題とは、データセットをグループに分割する問題です。

グループ内のデータは互いに似ており、異なるグループのデータとは異なる特徴を持っています。

この問題は、機械学習やデータマイニング、ネットワーク解析などの分野でよく用いられます。

クラスタリングによって得られたグループは、同じグループ内のデータが似ているため、そのグループに属するデータの特徴をより深く理解することができます。

また、異なるグループのデータの違いを明確にすることができます。

クラスタリングは、顧客分類、マーケティング分析、医療診断、画像処理、自然言語処理などの分野で幅広く使用されています。

例題

クラスタリング問題の例を１つ挙げます。

Zachary’s karate clubとして知られる、34人のメンバーとそのつながりを示すグラフを用いて、クラスタリングを行います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import networkx as nx
import matplotlib.pyplot as plt
from networkx.algorithms import community

# グラフの読み込み
G = nx.karate_club_graph()

# グラフの可視化
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
plt.show()

# クラスタリング
communities = community.greedy_modularity_communities(G)

# クラスタリング結果の表示
for i, c in enumerate(communities):
    print("Cluster ", i+1, ": ", c)

# クラスタリング結果をグラフに反映
color_map = []
for node in G:
    for i, c in enumerate(communities):
        if node in c:
            color_map.append(i)
nx.draw(G, pos, node_color=color_map, with_labels=True)
plt.show()

このコードでは、まずグラフを読み込み、可視化します。

次に、community.greedy_modularity_communities()を使用して、グラフをクラスタリングします。

最後に、クラスタリング結果をグラフに反映し、色分けして表示します。

この例では、Zachary’s karate clubグラフは3つのクラスターに分割されます。

各クラスターは、それぞれのメンバーのつながりを考慮して形成されていることがわかります。

[実行結果]

自然災害問題

自然災害に関する問題の一つとして、道路ネットワーク上での交通渋滞の発生があります。

以下のようなシナリオを考えてみましょう：

🔹ある地域において、地震が発生し、複数の道路が通行不能になった。
🔹この地域には複数の車両が存在し、それぞれの車両が目的地に到達するために、どのルートを取るかを決定しなければならない。
🔹通行可能なルートは限られており、道路の通行状況は車両数に応じて変化する。
🔹車両が選択するルートによって、交通渋滞が発生する可能性がある。

このような問題を解くために、以下のような手順でNetworkXを使用することができます。

1. 道路ネットワークのグラフを作成する。
   グラフのノードは交差点や道路の始点・終点とし、エッジは道路とし、エッジの重みはその道路の通行可能度合いとする。
2. 車両の現在地と目的地をノードとして指定する。
3. NetworkXの最短経路アルゴリズムを使用して、車両が最短時間で目的地に到達できる経路を計算する。
4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する。

解法・ソースコード

交通渋滞の発生確率を評価する上記の例題をnetworkxを用いて実装します。

具体的には、以下の手順でグラフを作成し、最短経路を計算して、最短経路上での交通渋滞の発生確率を評価しています。

1. グラフを作成する

1
2

G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5)])

まず、NetworkXを用いてグラフを作成します。ここでは、4つのノードと4つのエッジを持つグラフを作成しています。

2. エッジに重みを付ける

1
2

for (u, v) in G.edges():
    G[u][v]['weight'] = random.uniform(0.1, 1.0)

次に、各エッジにランダムな重みを付けます。

ここでは、0.1から1.0の範囲の乱数を用いて重みを設定しています。

3. ノード1からノード5への最短経路を計算する

1
2

path = nx.shortest_path(G, source=1, target=5, weight='weight')
print(f"Shortest path: {path}")

nx.shortest_path関数を用いて、ノード1からノード5までの最短経路を計算します。

weight引数には、エッジの重みを指定しています。

計算された最短経路をpath変数に格納し、print関数を用いて表示しています。

4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する

1
2
3
4
5
6
7
8

prob = 1.0
for i in range(len(path) - 1):
    u = path[i]
    v = path[i + 1]
    weight = G[u][v]['weight'] + random.uniform(-0.1, 0.1)
    G[u][v]['weight'] = max(weight - 0.1, 0)  # 通行可能度合いを減少させる
    prob *= weight  # 経路上のエッジの通行可能度合いの積を計算する
print(f"Probability of traffic congestion: {1 - prob:.3f}")

最後に、計算された最短経路上での交通渋滞の発生確率を評価します。

prob変数には、経路上のエッジの通行可能度合いの積を格納します。

forループで、最短経路上の各エッジについて、エッジの通行可能度合いをランダムに減少させ、prob変数にそのエッジの通行可能度合いを乗じます。

最後に、1 - probを計算することで、交通渋滞の発生確率を評価します。

なお、エッジの通行可能度合いの減少幅は、0から0.1の範囲の乱数を用いて決定しています。

以上の手順で、最短経路上での交通渋滞の発生確率を評価することができます。

[実行結果（例）]

Shortest path: [1, 2, 4, 5]
Probability of traffic congestion: 0.953

ノード1からノード5への最短経路は[1, 2, 4, 5]となりました。

そして、この経路上のエッジの通行可能度合いの積を計算することで、交通渋滞の発生確率を評価しました。

結果として、この経路上で交通渋滞が発生する確率は0.953となりました。

最小全域木問題

最小全域木問題 (Minimum Spanning Tree Problem) とは、グラフ理論において、与えられた重みつき無向グラフに対して、そのグラフの全ての頂点を含む木（連結かつ閉路を持たないグラフ）のうち、辺の重みの和が最小になるような木を求める問題です。

問題

以下の図のグラフにおいて、全ての頂点を繋ぐ最小コストの辺集合を求めてください。

     2     3
 A ----- B ----- C
 |   4 / |   5 / |
 |   /   |   /   |
 1 /     4 /     | 1
 | /     | /     |
 |/      |/      |
 D ----- E ----- F
     5     4

解法・ソースコード

最初に、networkxライブラリをnxという名前でインポートします。

次に、空のグラフを作成し、add_weighted_edges_from()メソッドで、頂点間の辺を加えます。

ここで、(‘A’, ‘B’, 2)というように、3つ目の引数で辺の重みを指定しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import networkx as nx

# グラフを作成
G = nx.Graph()
G.add_weighted_edges_from([
    ('A', 'B', 2),
    ('A', 'D', 1),
    ('B', 'C', 3),
    ('B', 'E', 4),
    ('B', 'D', 4),
    ('C', 'E', 5),
    ('C', 'F', 1),
    ('D', 'E', 5),
    ('E', 'F', 4)
])

次に、minimum_spanning_tree()メソッドを使って、最小全域木を求めます。

このメソッドは、引数にグラフを取り、最小全域木を構成する辺集合を返します。

最後に、print()関数を使って、最小全域木を構成する辺集合を表示しています。

edges()メソッドを使うことで、辺集合を取得できます。

1
2
3
4
5

# 最小全域木を求める
mst = nx.minimum_spanning_tree(G)

# 結果を表示
print(mst.edges())

実行すると、以下のように最小全域木を構成する辺集合が表示されます。

[実行結果]

[('A', 'D'), ('A', 'B'), ('B', 'C'), ('B', 'E'), ('E', 'F')]

影響力の分析

影響力の分析についての例題として、Twitter上でのフォロー関係から、影響力の高いユーザーを分析することを考えてみます。

以下のようなツイッターユーザー間のフォロー関係があるとします。

A follows B
A follows C
B follows C
B follows D
C follows A
C follows B
C follows D
D follows A
D follows C

このグラフをNetworkXで表現し、pagerankアルゴリズムを用いて、各ユーザーの影響力を計算するPythonコードを以下に示します。

pagerankアルゴリズムとは、Webページの重要度を計算するアルゴリズムです。

Webページのリンク構造を解析して、そのページが他の多くのページからどの程度の重要度を持つかを計算します。

これを、フォロワー関係からの影響力を分析するのに使ってみます。

[ソースコード]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import networkx as nx

# ツイッターユーザーのフォロー関係を表現するグラフを作成する
G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'C')])

# pagerankアルゴリズムを用いて、各ユーザーの影響力を計算する
pagerank = nx.pagerank(G)

# 影響力が高い順にユーザーを並び替える
sorted_pagerank = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)

# 結果を表示する
for user, score in sorted_pagerank:
    print(f'{user}: {score}')

実行すると、以下のような結果が得られます。

[実行結果]

C: 0.3245609358176832
A: 0.2251463547274389
B: 0.2251463547274389
D: 0.2251463547274389

この結果から、ユーザーCが最も影響力が高いことが分かりました。

問題

以下のグラフにおいて、頂点Aと頂点Eの間にパスが存在するかどうかを判定してください。

  A --- B --- C
  |     |     |
  |     |     |
  D --- E --- F

解法・ソースコード

この問題を解くためには、以下の手順に従います。

1. NetworkXを用いてグラフを作成します。

1
2
3
4
5

import networkx as nx

G = nx.Graph()

G.add_edges_from([('A', 'B'), ('A', 'D'), ('B', 'C'), ('B', 'E'), ('C', 'F'), ('D', 'E'), ('E', 'F')])

2. 頂点Aと頂点Eの間にパスが存在するかどうかを判定します。

NetworkXのhas_path関数を使います。

1
2
3
4

if nx.has_path(G, 'A', 'E'):
    print("頂点Aと頂点Eの間にパスが存在します。")
else:
    print("頂点Aと頂点Eの間にパスは存在しません。")

実行結果は、「頂点Aと頂点Eの間にパスが存在します。」となります。

以上の手順で、グラフにおいて2つの頂点間にパスが存在するかどうかを判定することができました。