基于Python实现LFM种子传播算法

基于Python2.7实现的LFM种子传播算法。　参考论文　LFM：Detecting the overlapping and hierarchical community structure in complex networks

# -*- coding: UTF-8 -*-

“““
Created on 18-4-7

@summary: ＬＦＭ算法实现　种子传播算法

@author: dreamhome
“““

import random
import get_graph


class Community（object）:
    “““
    定义扩展的社区
    “““

    def __init__（self graph alpha=1.0）:
        “““
        社区属性
        :param graph:
        :param alpha:
        “““
        self._graph = graph
        self._alpha = alpha
        self._nodes = set（）
        self._k_in = 0
        self._k_out = 0

    def add_node（self node）:
        “““
        子社团中加入节点　改变子社团的出度和入度
        :param node:
        :return:
        “““
        neighbors = set（self._graph.neighbors（node））
        node_k_in = len（neighbors & self._nodes）
        node_k_out = len（neighbors） - node_k_in
        self._nodes.add（node）
        self._k_in += 2 * node_k_in
        self._k_out = self._k_out + node_k_out - node_k_in

    def remove_vertex（self node）:
        “““
        删除节点
        :param node:
        :return:
        “““
        neighbors = set（self._graph.neighbors（node））
        community_nodes = self._nodes
        node_k_in = len（neighbors & community_nodes）
        node_k_out = len（neighbors） - node_k_in
        self._nodes.remove（node）
        self._k_in -= 2 * node_k_in
        self._k_out = self._k_out - node_k_out + node_k_in

    def cal_add_fitness（self node）:
        “““
        计算添加节点后适应度的变化
        :param node:
        :return:
        “““
        neighbors = set（self._graph.neighbors（node））
        old_k_in = self._k_in
        old_k_out = self._k_out
        vertex_k_in = len（neighbors & self._nodes）
        vertex_k_out = len（neighbors） - vertex_k_in
        new_k_in = old_k_in + 2 * vertex_k_in
        new_k_out = old_k_out + vertex_k_out - vertex_k_in
        new_fitness = new_k_in / （new_k_in + new_k_out） ** self._alpha
        old_fitness = old_k_in / （old_k_in + old_k_out） ** self._alpha
        return new_fitness - old_fitness

    def cal_remove_fitness（self node）:
        “““
        计算删除节点后适应度的变化
        :param node:
        :return:
        “““
        neighbors = set（self._graph.neighbors（node））
        new_k_in = self._k_in
        new_k_out = self._k_out
        node_k_in = len（neighbors & self._nodes）
        node_k_out = len（neighbors） - node_k_in
        old_k_in = new_k_in - 2 * node_k_in
        old_k_out = new_k_out - node_k_out + node_k_in
        old_fitness = old_k_in / （old_k_in + old_k