基于LFM的重叠社区发现算法python代码实现

本文主要是介绍基于LFM的重叠社区发现算法python代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基于LFM的重叠社区发现算法python代码实现

import random
import networkx as nx
import matplotlib.pyplot as plt
import zipfile
#import urllib.request as urllib
class Community():''' use set operation to optimize calculation '''def __init__(self,G,alpha=1.0):self._G = Gself._alpha = alphaself._nodes = set()self._k_in = 0self._k_out = 0def add_node(self,node):neighbors = set(self._G.neighbors(node))#print("添加令居节点",neighbors , self._nodes,neighbors & self._nodes)node_k_in = len(neighbors & self._nodes)#neighbor和self._nodes公有节点的数目存入node_k_in#print("node_k_in",node_k_in)node_k_out = len(neighbors) - node_k_in#print("node_k_out",node_k_out)self._nodes.add(node)self._k_in += 2*node_k_inself._k_out = self._k_out+node_k_out-node_k_indef remove_node(self,node):neighbors = set(self._G.neighbors(node))community_nodes = self._nodes#print("community_nodes",community_nodes)node_k_in = len(neighbors & community_nodes)node_k_out = len(neighbors) - node_k_inself._nodes.remove(node)self._k_in -= 2*node_k_inself._k_out = self._k_out - node_k_out+node_k_indef cal_add_fitness(self,node):#fitness适应度neighbors = set(self._G.neighbors(node))old_k_in = self._k_inold_k_out = self._k_outvertex_k_in = len(neighbors & self._nodes)#vertex顶点vertex_k_out = len(neighbors) - vertex_k_in new_k_in = old_k_in + 2*vertex_k_innew_k_out = old_k_out + vertex_k_out-vertex_k_innew_fitness = new_k_in/(new_k_in+new_k_out)**self._alpha#幂次old_fitness = old_k_in/(old_k_in+old_k_out)**self._alphareturn new_fitness-old_fitnessdef cal_remove_fitness(self,node):neighbors = set(self._G.neighbors(node))new_k_in = self._k_innew_k_out = self._k_outnode_k_in = len(neighbors & self._nodes)node_k_out = len(neighbors) - node_k_inold_k_in = new_k_in - 2*node_k_inold_k_out = new_k_out - node_k_out + node_k_inold_fitness = old_k_in/(old_k_in+old_k_out)**self._alpha new_fitness = new_k_in/(new_k_in+new_k_out)**self._alphareturn new_fitness-old_fitnessdef recalculate(self):for vid in self._nodes:fitness = self.cal_remove_fitness(vid)if fitness < 0.0:return vidreturn Nonedef get_neighbors(self):neighbors = set()for node in self._nodes:neighbors.update(set(self._G.neighbors(node)) - self._nodes)return neighborsdef get_fitness(self):return float(self._k_in)/((self._k_in+self._k_out) ** self._alpha)class LFM():def __init__(self, G, alpha):self._G = Gself._alpha = alphadef execute(self):communities = []print("嘿嘿",list(self._G.node.keys()))print("---------------------")node_not_include = list(self._G.node.keys())while(len(node_not_include) != 0):c = Community(self._G, self._alpha)#print("self._alpha",self._alpha)#0.9# randomly select a seed nodeseed = random.choice(node_not_include)c.add_node(seed)print("随机选取节点是：",seed)to_be_examined = c.get_neighbors()print("c.get_neighbors()",c.get_neighbors())while(to_be_examined):#largest fitness to be addedm = {}for node in to_be_examined:fitness = c.cal_add_fitness(node)#计算点的适应度》0加入，小于0删除m[node] = fitnessto_be_add = sorted(m.items(),key=lambda x:x[1],reverse = True)[0]#啥意思？？？#适应度降序排列#stop conditionif(to_be_add[1] < 0.0):breakc.add_node(to_be_add[0])to_be_remove = c.recalculate()while(to_be_remove != None):c.remove_node(to_be_remove)to_be_remove = c.recalculate()to_be_examined = c.get_neighbors()for node in c._nodes:if(node in node_not_include):node_not_include.remove(node)communities.append(c._nodes)return communitiesif(__name__ == "__main__"):#G = nx.karate_club_graph()#一个边集一个点集# G = nx.florentine_families_graph()zf = zipfile.ZipFile('football.zip')  # zipfile objecttxt = zf.read('football.txt').decode()  # read info filegml = zf.read('football.gml').decode()  # read gml data# throw away bogus first line with # from mejn filesgml = gml.split('\n')[1:]G = nx.parse_gml(gml)  # parse gml dataprint(txt)# print degree for each team - number of gamesfor n, d in G.degree():print('%s %d' % (n, d))options = {'node_color': 'red','node_size': 50,'line_color': 'grey','linewidths': 0,'width': 0.1,}nx.draw(G, **options)#networkx.draw(G, with_labels=True)plt.show()algorithm = LFM(G,0.9)communities = algorithm.execute()for c in communities:print (len(c),sorted(c))