#?-*-?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