تحلیل ارتباط‌های شبکه‌های اجتماعی با کوساراجو

توی این پست می‌خوام یکی از کاربردی‌ترین الگوریتم‌های گراف رو با زبونی ساده، البته با رویکردی دقیق و در نهایت با کد C++ یاد بگیریم: الگوریتم دو مرحله‌ای DFS یا Kosaraju’s Algorithm.

برای درک بهتر، همه‌چیز رو با یک مثال شبکه‌ی اجتماعی فرضی‌مون، فریفید، پیش می‌بریم.

سناریو: ارتباط‌ کاربران توی فریفید

فرض کنید فریفید یک شبکه‌ی اجتماعیه که توی اون کاربرا می‌تونند همدیگر رو دنبال کنند. این دنبال‌کردن‌ها یک گراف جهت‌دار تشکیل می‌ده:

• اگر علی، سارا رو دنبال کند، یک یال از علی به سارا داریم:
  \(\text{Ali} \to \text{Sara}\)
• اگر سارا هم علی را دنبال کند، بین آن‌ها ارتباط دوطرفه است.

می‌خواهیم گروه‌هایی از کاربران رو پیدا کنیم که بتونند به هم دسترسی داشته باشن، یعنی از هر کدام بشه به دیگری رسید یا برعکس. این گروه‌ها همان اجزای قویا همبند (SCC) ‌اند.

ایده‌ی دو مسیر از DFS

ما برای حل این مساله از الگوریتم کوساراجو استفاده می‌کنیم که از دو مسیر DFS استفاده می‌کند:

مرحله اول: DFS روی گراف اصلی

• همه‌ی راس‌ها را با DFS پیمایش می‌کنیم.
• هر بار که DFS از یک گره تمام شد، اون رو توی یک پشته قرار می‌دیم (بر اساس زمان پایان).

مرحله دوم: DFS روی گراف معکوس‌شده

• گراف رو معکوس می‌کنیم (یال‌ها رو برعکس می‌کنیم).
• حالا راس‌ها رو به‌ترتیب از روی پشته برمی‌داریم و DFS می‌زنیم.
• هر بار که DFS جدید شروع می‌شه، یک کامپوننت قویا همبند کشف می‌شه.

تعریف ریاضی مساله

• گراف جهت‌دار:
  \(G = (V, E)\)
• گراف معکوس:
  \(G^T = (V, E^T), \quad (u, v) \in E \Rightarrow (v, u) \in E^T\)
  که در آن یال‌ها جهت شان معکوس شده.
• هدف:
  یافتن تمام زیرمجموعه‌های \( C_1, C_2, \dots, C_k \subseteq V \) که:
  \(\forall u, v \in C_i:\ u \leadsto v \text{ و } v \leadsto u\)

پیاده‌سازی الگوریتم Kosaraju توی C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1e5 + 5;

vector<int> G[MAXN], GT[MAXN]; // G: original graph, GT: transposed graph
bool visited[MAXN];
stack<int> order;
vector<vector<int>> components;

// First DFS: to fill the order stack with finish times
void dfs1(int u) {
    visited[u] = true;
    for (int v : G[u])
        if (!visited[v])
            dfs1(v);
    order.push(u);
}

// Second DFS: to collect components from the transposed graph
void dfs2(int u, vector<int>& comp) {
    visited[u] = true;
    comp.push_back(u);
    for (int v : GT[u])
        if (!visited[v])
            dfs2(v, comp);
}

int main() {
    int n, m;
    cin >> n >> m; // Number of nodes and edges

    // Reading the edges and building the graph and its transpose
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        GT[v].push_back(u); // Reverse the edge for the transposed graph
    }

    // First pass: DFS on the original graph to get finish times
    fill(visited, visited + n + 1, false);
    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            dfs1(i);

    // Second pass: DFS on the transposed graph in reverse order
    fill(visited, visited + n + 1, false);
    while (!order.empty()) {
        int u = order.top();
        order.pop();
        if (!visited[u]) {
            vector<int> comp;
            dfs2(u, comp);
            components.push_back(comp);
        }
    }

    // Output the Strongly Connected Components
    cout << “Strongly Connected Components:\n”;
    for (const auto& comp : components) {
        for (int u : comp)
            cout << u << ” “;
        cout << “\n”;
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1e5 + 5;

vector<int> G[MAXN], GT[MAXN]; // G: original graph, GT: transposed graph
bool visited[MAXN];
stack<int> order;
vector<vector<int>> components;

// First DFS: to fill the order stack with finish times
void dfs1(int u) {
    visited[u] = true;
    for (int v : G[u])
        if (!visited[v])
            dfs1(v);
    order.push(u);
}

// Second DFS: to collect components from the transposed graph
void dfs2(int u, vector<int>& comp) {
    visited[u] = true;
    comp.push_back(u);
    for (int v : GT[u])
        if (!visited[v])
            dfs2(v, comp);
}

int main() {
    int n, m;
    cin >> n >> m; // Number of nodes and edges

    // Reading the edges and building the graph and its transpose
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        GT[v].push_back(u); // Reverse the edge for the transposed graph
    }

    // First pass: DFS on the original graph to get finish times
    fill(visited, visited + n + 1, false);
    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            dfs1(i);

    // Second pass: DFS on the transposed graph in reverse order
    fill(visited, visited + n + 1, false);
    while (!order.empty()) {
        int u = order.top();
        order.pop();
        if (!visited[u]) {
            vector<int> comp;
            dfs2(u, comp);
            components.push_back(comp);
        }
    }

    // Output the Strongly Connected Components
    cout << “Strongly Connected Components:\n”;
    for (const auto& comp : components) {
        for (int u : comp)
            cout << u << ” “;
        cout << “\n”;
    }

    return 0;
}

یک مثال ساده

فرض کن ورودی این باشه:

5 5
1 2
2 3
3 1
3 4
5 4

5 5
1 2
2 3
3 1
3 4
5 4

این گراف سه SCC دارد:

• \(\{1, 2, 3\}\)
• \(\{4\}\)
• \(\{5\}\)

پیچیدگی زمانی

• زمان اجرای کل الگوریتم: \(O(V + E)\) چون دو بار DFS کامل انجام می‌دهیم و گراف معکوس هم در زمان خطی ساخته می‌شود.

نتیجه‌ی عملی در شبکه‌ی اجتماعی ما:

با استفاده از الگوریتم Kosaraju، فریفید می‌تونه گروه‌هایی از کاربران رو پیدا کنه که عملاً یه حباب اجتماعی (social bubble) تشکیل دادن: یعنی اگه یکی از اعضای این گروه پست یا پیام بفرسته، به‌نوعی همهٔ اعضای اون گروه می‌تونن ازش باخبر بشن، چون ارتباطات بین‌شون دوطرفه‌ست (از نظر دسترسی گرافی).

مثال کاربردی:

مثلن فرض کن یه ویژگی به اسم “گفت‌وگوی گروهی خودکار” یا “پیشنهاد پست خودکار” توی فریفید اضافه بشه.
با پیدا کردن SCCها:

• می‌فهمیم چه کاربرهایی به‌طور طبیعی یه گروه تشکیل دادن.
• می‌تونیم پست اونا رو به هم پیشنهاد بدیم.
• یا حتی یک گفت‌وگوی گروهی بین‌شون باز کنیم، چون از نظر تعاملات، واقعن به هم دسترسی دارن.

نتیجه فنی برای توسعه‌دهنده‌ها:

SCCها به ما کمک می‌کنن:

• تشخیص خوشه‌های متصل اجتماعی
• تحلیل نفوذ (Influence Propagation) داخل گروه‌ها
• بهینه‌سازی نمایش فیدها یا نوتیفیکیشن‌ها
• ایجاد ویژگی‌های “Friend Suggestion” یا “Community Detection”

جمع‌بندی:

الگوریتم Kosaraju فقط یه ترفند الگوریتمی نیست؛ توی شبکه‌های اجتماعی؛ اینجا برای مثل فریفید می‌تونه پایه‌ی تصمیم‌گیری خیلی از قابلیت‌های هوشمند باشه. گروه‌هایی که از نظر گرافی به‌هم وصله‌اند، از نظر اجتماعی هم به هم نزدیک‌ترند و می‌تونن فرصت‌های زیادی برای تعامل خلق کنند.