c++实现Louvain算法

以下是C++实现Louvain算法的步骤：

1.定义节点和边的数据结构

struct Node {
    int id; // 节点id
    int community; // 所属社区
    int degree; // 节点度数
    vector<int> neighbors; // 相邻节点
};

struct Edge {
    int src; // 边的起点
    int dst; // 边的终点
    int weight; // 边的权重
};

2.读取图数据并初始化节点和边

vector<Node> nodes;
vector<Edge> edges;

// 读取图数据并初始化节点和边
// ...

// 初始化节点的社区为自身
for (int i = 0; i < nodes.size(); i++) {
    nodes[i].community = i;
}

// 初始化每个节点的度数
for (int i = 0; i < edges.size(); i++) {
    nodes[edges[i].src].degree += edges[i].weight;
    nodes[edges[i].dst].degree += edges[i].weight;
}

3.定义计算模块度Q函数的函数

double calcModularity(vector<Node>& nodes, vector<Edge>& edges) {
    double q = 0.0;
    double m = 0.0;

    // 计算总权重
    for (int i = 0; i < edges.size(); i++) {
        m += edges[i].weight;
    }

    // 计算每个社区的模块度
    for (int i = 0; i < nodes.size(); i++) {
        for (int j = 0; j < nodes.size(); j++) {
            if (nodes[i].community == nodes[j].community) {
                double ki = nodes[i].degree;
                double kj = nodes[j].degree;
                double aij = 0.0;

                // 计算节点i和节点j之间的边权重
                for (int k = 0; k < edges.size(); k++) {
                    if ((edges[k].src == i && edges[k].dst == j) || (edges[k].src == j && edges[k].dst == i)) {
                        aij = edges[k].weight;
                        break;
                    }
                }

                q += (aij - ki * kj / (2 * m)) / (2 * m);
            }
        }
    }

    return q;
}

4.定义计算节点移动后的模块度增量的函数

double calcDeltaQ(Node& node, int community, vector<Node>& nodes, vector<Edge>& edges) {
    double deltaQ = 0.0;
    double m = 0.0;

    // 计算总权重
    for (int i = 0; i < edges.size(); i++) {
        m += edges[i].weight;
    }

    // 计算节点移动后的模块度增量
    for (int i = 0; i < node.neighbors.size(); i++) {
        int neighbor = node.neighbors[i];
        int oldCommunity = nodes[neighbor].community;

        double ki = node.degree;
        double kj = nodes[neighbor].degree;
        double aij = 0.0;

        // 计算节点i和节点j之间的边权重
        for (int j = 0; j < edges.size(); j++) {
            if ((edges[j].src == node.id && edges[j].dst == neighbor) || (edges[j].src == neighbor && edges[j].dst == node.id)) {
                aij = edges[j].weight;
                break;
            }
        }

        double deltaQij = 0.0;

        if (community == oldCommunity) {
            deltaQij = (aij - ki * kj / (2 * m)) / m;
        } else {
            deltaQij = (-aij + ki * kj / (2 * m)) / m;
        }

        deltaQ += deltaQij;
    }

    return deltaQ;
}

5.定义节点移动函数

void moveNode(Node& node, int community, vector<Node>& nodes, vector<Edge>& edges) {
    int oldCommunity = node.community;

    // 更新节点的社区
    node.community = community;

    // 更新节点的相邻节点的度数
    for (int i = 0; i < node.neighbors.size(); i++) {
        int neighbor = node.neighbors[i];

        nodes[neighbor].degree -= edges[i].weight;

        if (nodes[neighbor].community == oldCommunity) {
            nodes[neighbor].degree += edges[i].weight;
        } else if (nodes[neighbor].community == community) {
            nodes[neighbor].degree += edges[i].weight;
        }
    }
}

6.定义Louvain算法函数

void louvain(vector<Node>& nodes, vector<Edge>& edges) {
    bool isMoved = true;

    while (isMoved) {
        isMoved = false;

        for (int i = 0; i < nodes.size(); i++) {
            Node& node = nodes[i];
            int oldCommunity = node.community;
            int bestCommunity = oldCommunity;
            double maxDeltaQ = 0.0;

            // 遍历节点的相邻节点，计算节点移动后的模块度增量
            for (int j = 0; j < node.neighbors.size(); j++) {
                int neighbor = node.neighbors[j];
                double deltaQ = calcDeltaQ(node, nodes[neighbor].community, nodes, edges);

                if (deltaQ > maxDeltaQ) {
                    maxDeltaQ = deltaQ;
                    bestCommunity = nodes[neighbor].community;
                }
            }

            // 如果节点移动后的模块度增量大于0，则移动节点
            if (maxDeltaQ > 0.0) {
                moveNode(node, bestCommunity, nodes, edges);
                isMoved = true;
            }
        }
    }
}