ソーシャルグラフ（Facebook/LinkedIn）── 6次の隔たりとグラフDB
扱うCS概念：グラフ表現（隣接リスト vs 隣接行列）、BFS（幅優先探索）、グラフシャーディング、グラフデータベース（Neo4j）
この章で何ができるようになるか：「友達の友達を探す」「コネクションの深さを求める」という操作の背後にあるデータ構造と、10億ノードのグラフをどう分散管理するかを説明できるようになる。
問題設定
LinkedIn のソーシャルグラフ機能を設計する。
要件：
- ユーザー数：10億人
- コネクション数：平均500件/ユーザー（エッジ総数：2500億本）
- 機能1：「あなたとAさんは何次のつながりか」（接続距離）
- 機能2：「共通のつながりは誰か」（共通友人）
- 機能3：「Aさんを知っているかもしれない人」（友達推薦）
- レスポンスタイム：500ms 以内
規模感の難しさ：
10億ノード × 平均500エッジ ÷ 2（無向グラフ）= 2500億の関係性
これをRDBMSの JOIN で都度計算するのは現実的でないグラフの表現方法
グラフを格納する方法は大きく2つある。
隣接行列（Adjacency Matrix）
Alice Bob Carol Dave
Alice [ 0 1 1 0 ]
Bob [ 1 0 0 1 ]
Carol [ 1 0 0 1 ]
Dave [ 0 1 1 0 ]
cell[i][j] = 1 → i と j はコネクション- ✅ 「Alice と Bob はつながっているか」が O(1)
- ❌ 10億ユーザーなら 10^18 セル → 保存不可能
- ❌ コネクションは疎（sparse）なのに全組み合わせを持つのは無駄
隣接リスト（Adjacency List）← ソーシャルグラフに使われる
graph = {
"alice": ["bob", "carol"],
"bob": ["alice", "dave"],
"carol": ["alice", "dave"],
"dave": ["bob", "carol"],
}- ✅ 実際のコネクションのみ保存（疎グラフに最適）
- ✅ ユーザーの友達一覧が O(degree)で取得できる
- ❌ 「AとBはつながっているか」は O(degree) のリニアサーチ（ハッシュセット化で O(1)）
実際のシステムでは隣接リストをRDBMS・KVストア・グラフDBで表現する：
-- RDBMSでの実装
CREATE TABLE connections (
user_id_a BIGINT NOT NULL,
user_id_b BIGINT NOT NULL,
created_at TIMESTAMP,
PRIMARY KEY (user_id_a, user_id_b),
INDEX idx_b_a (user_id_b, user_id_a) -- 双方向検索のため
);
-- 無向グラフ：常に user_id_a < user_id_b で格納して重複を防ぐBFS（幅優先探索）：接続距離と共通友人
「Alice と Dave の接続距離を求める」= グラフの最短経路問題（重みなし）。BFS が最適だ。
from collections import deque
def get_connection_degree(graph: dict, start: str, target: str) -> int | None:
"""
BFS で start から target までの最短距離（次数）を返す
LinkedIn の「1次 / 2次 / 3次+」に相当
"""
if start == target:
return 0
visited = {start}
queue = deque([(start, 0)]) # (ノード, 距離)
while queue:
node, distance = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor == target:
return distance + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
return None # つながっていない
# 共通友人：2つのコネクションセットの積集合
def get_mutual_connections(graph: dict, user_a: str, user_b: str) -> set[str]:
friends_a = set(graph.get(user_a, []))
friends_b = set(graph.get(user_b, []))
return friends_a & friends_b # 積集合（O(min(|A|, |B|))）双方向BFS（Bidirectional BFS）：10億ノードのグラフに素朴な BFS を使うと、2次のコネクションで 500^2 = 25万ノード を探索する。6次なら 500^6 = 15兆 — 現実的でない。
双方向BFSはスタートとゴールの両端から同時に探索し、出会った時点で終了する。
def bidirectional_bfs(graph: dict, start: str, target: str) -> int | None:
"""
両端から同時に BFS を進め、出会った時点の距離を返す
探索ノード数を大幅削減（O(b^(d/2)) vs O(b^d)、b=分岐係数、d=深さ）
"""
if start == target:
return 0
# 各端からの訪問済みセット（{ノード: その深さ}）
visited_from_start = {start: 0}
visited_from_end = {target: 0}
queue_start = deque([start])
queue_end = deque([target])
depth_start = depth_end = 0
while queue_start or queue_end:
# スタート側を1層進める
if queue_start:
depth_start += 1
next_level = []
while queue_start:
node = queue_start.popleft()
for neighbor in graph.get(node, []):
if neighbor not in visited_from_start:
visited_from_start[neighbor] = depth_start
next_level.append(neighbor)
# ゴール側の探索済みと交差したら終了
if neighbor in visited_from_end:
return depth_start + visited_from_end[neighbor]
queue_start = deque(next_level)
# ゴール側を1層進める（同様）
if queue_end:
depth_end += 1
next_level = []
while queue_end:
node = queue_end.popleft()
for neighbor in graph.get(node, []):
if neighbor not in visited_from_end:
visited_from_end[neighbor] = depth_end
next_level.append(neighbor)
if neighbor in visited_from_start:
return visited_from_start[neighbor] + depth_end
queue_end = deque(next_level)
return None素朴なBFSの探索ノード数（分岐係数500、深さ6）:
500^6 ≈ 15 兆ノード
双方向BFSの探索ノード数（深さ3+3）:
2 × 500^3 ≈ 2.5 億ノード → 6万倍の差！グラフシャーディング：10億ノードをどう分散するか
グラフを複数のサーバーに分割する（シャーディング）には、グラフ特有の難しさがある。
RDBMSのシャーディングと何が違うのか：
通常のシャーディング（例：user_id % N）：
user_id=1 → サーバー1
user_id=2 → サーバー2
→ 各ユーザーのデータはそれぞれのサーバーに独立して存在
グラフのシャーディング：
AliceはサーバーA、BobはサーバーBにいる
→ AliceとBobのコネクションを辿るたびに サーバーA ↔ サーバーB の通信が発生
→ BFSのたびに大量のクロスサーバー通信 → レイテンシが爆発理想的なグラフパーティショニング：「よく一緒に使われるノード（コミュニティ）を同じサーバーに入れる」。
graph LR
subgraph Server1（東京コミュニティ）
A[Alice] --- B[Bob]
B --- C[Carol]
A --- C
end
subgraph Server2（大阪コミュニティ）
D[Dave] --- E[Eve]
E --- F[Frank]
end
C -.->|クロスサーバーエッジ| Dコミュニティを同じサーバーに寄せると、クロスサーバー通信を最小化できる。これは グラフ分割問題（Graph Partitioning Problem） だが、最適解を求めるのは NP 困難。実際は近似アルゴリズム（METIS など）を使う。
Facebook の実際のアプローチ（TAO）：TAO は地理的に分散したキャッシュ階層（follower → leader → storage の2層キャッシュ）を使い、同じ地域のリクエストを同じキャッシュクラスタで処理することでローカリティを活用している。完全な最適化はせず、キャッシュ層でアクセスの局所性を高めることで十分なパフォーマンスを得ている。
⚠️ 検証注記: TAO の 2013年の論文（USENIX ATC ‘13）では、シャーディング戦略としてはデータを数十万のシャードに分割し同一シャードのデータを同じ MySQL データベースに格納する方式が記述されていますが、「同じ地域のユーザーを同じシャードに配置する」という具体的な戦略は論文中で明示されていません。上記の記述は TAO のキャッシュ階層による地理的ローカリティの活用として修正しました。
グラフデータベース（Neo4j）
RDBMSでグラフを扱う場合、深い JOIN が必要になる。
-- 「3次のつながり」をRDBMSで求める
SELECT DISTINCT c3.user_id_b
FROM connections c1
JOIN connections c2 ON c1.user_id_b = c2.user_id_a
JOIN connections c3 ON c2.user_id_b = c3.user_id_a
WHERE c1.user_id_a = :user_id
AND c3.user_id_b != :user_id;
-- JOIN が深くなるほど指数的に遅くなるグラフDBはノードとエッジをネイティブに格納し、ポインタを辿る（ネイティブグラフ探索） だけでトラバーサルができる。
-- Neo4j の Cypher クエリ
-- 「AliceからBobまでの最短経路」
MATCH path = shortestPath(
(alice:User {name: "Alice"})-[*]-(bob:User {name: "Bob"})
)
RETURN length(path) AS degree, [n in nodes(path) | n.name] AS path_names;
-- 「共通のつながり」
MATCH (alice:User {name: "Alice"})-[:CONNECTED]-(mutual)-[:CONNECTED]-(bob:User {name: "Bob"})
WHERE alice <> bob
RETURN mutual.name AS mutual_connection, count(*) AS strength
ORDER BY strength DESC;
-- 「友達かもしれない人（友達の友達で、まだつながっていない）」
MATCH (me:User {name: "Alice"})-[:CONNECTED]-()-[:CONNECTED]-(suggested:User)
WHERE NOT (me)-[:CONNECTED]-(suggested)
AND me <> suggested
RETURN suggested.name, count(*) AS common_friends
ORDER BY common_friends DESC
LIMIT 10;グラフDB vs RDBMS の選択：
| RDBMS | グラフDB（Neo4j） | |
|---|---|---|
| 深いトラバーサル（3〜6次） | ❌ JOIN が指数的に遅い | ✅ ポインタ追跡で高速 |
| シンプルなエンティティ管理 | ✅ 得意 | △ オーバーキル |
| スケールアウト | ✅ シャーディング確立済み | △ 分散が難しい |
| クエリ言語 | SQL（親しみやすい） | Cypher（グラフ専用、直感的） |
| 向いているユースケース | ユーザー管理・注文管理 | ソーシャル・不正検知・推薦 |
友達推薦：グラフ理論の応用
「知り合いかも（People You May Know）」は LinkedIn・Facebook の核心機能だ。
最もシンプルで効果的な手法：共通友人の数が多い人を推薦する。
def people_you_may_know(graph: dict, user: str, top_k: int = 10) -> list[tuple[str, int]]:
my_friends = set(graph.get(user, []))
candidates: dict[str, int] = {} # {候補ユーザー: 共通友人数}
for friend in my_friends:
for fof in graph.get(friend, []): # 友達の友達
if fof != user and fof not in my_friends:
candidates[fof] = candidates.get(fof, 0) + 1
# 共通友人数で降順ソートして Top-K を返す
return sorted(candidates.items(), key=lambda x: -x[1])[:top_k]
# 使用例
graph = {
"alice": ["bob", "carol", "dave"],
"bob": ["alice", "eve", "frank"],
"carol": ["alice", "eve"],
"dave": ["alice", "frank"],
"eve": ["bob", "carol"],
"frank": ["bob", "dave"],
}
print(people_you_may_know(graph, "alice"))
# → [("eve", 2), ("frank", 2)]
# Eve: alice→bob→eve, alice→carol→eve（共通2人）
# Frank: alice→bob→frank, alice→dave→frank（共通2人）より高度な推薦には Jaccard 係数 や Adamic/Adar 指標 が使われる：
def adamic_adar_score(graph: dict, user_a: str, user_b: str) -> float:
"""
共通友人のスコアに「その友人が持つコネクション数の逆数」で重み付け。
「珍しいコネクションを共有している方が、関係が強い」という直感。
"""
friends_a = set(graph.get(user_a, []))
friends_b = set(graph.get(user_b, []))
common = friends_a & friends_b
score = 0.0
for mutual in common:
degree = len(graph.get(mutual, []))
if degree > 1:
score += 1 / math.log(degree) # 次数が高い人の共通は価値が低い
return scoreまとめ
| 機能 | アルゴリズム | 計算量 |
|---|---|---|
| 接続距離（1次/2次/3次） | 双方向BFS | O(b^(d/2)) |
| 共通友人 | 積集合（ハッシュセット） | O(min(deg_a, deg_b)) |
| 友達推薦 | 友達の友達カウント / Adamic-Adar | O(deg × avg_deg) |
| グラフ格納 | 隣接リスト（KVストア/グラフDB） | — |
| 深いトラバーサル | グラフDB（Neo4j Cypher） | O(depth × avg_degree) |
ソーシャルグラフの設計で最も難しいのは「どこでグラフを切るか（シャーディング）」だ。グラフは本質的に要素間の依存関係の塊であり、きれいに分割できない。この制約を受け入れた上で「よく使われるパスをいかに局所的に保つか」を工夫することが設計の核心になる。