Community aware random walk for network embedding
该文中提出了一中网络嵌入方法，来解决本地和全局的网络结构信息的保留。
可以简单的理解为：通过算法2来从整个图中随机游走获得游走序列，然后将这个序列输入到Skip-gram算法中， 然后可以得到该序列的一个vxd中的一个行或者列向量表示（算法1），最终这些向量构成U矩阵，也就是整个网络的网络嵌入表示。
在2019年，本文作者将这个方法应用在了Influence maximization across heterogeneous interconnected networks based on deep learning一文中，它的表示框架在该文中表示如下：
其实可以看出，在该文中的应用其实也就是基于社区认知的随机游走算法，而非整个网络的嵌入表示，即：CommunityawareRW。下面就简单实现下这个算法：
CommunityawareRW.py
import randomclass RandomWalk(object):def __init__(self, G, v, Com, l, alpha):"""初始化参数:param G: 图数据，类型为 nx.Graph():param v: 当前游走的起点:param Com: 节点v所在的社区列表 list:param l: 随机游走的长度:param alpha: 随机阈值变量"""self.G = Gself.v = vself.Com = Comself.l = lself.alpha = alphadef initialize(self):"""初始随机游走的路径存储列表，并将当前节点存入该列表中initialize RW with v"""self.RW = [self.v]def hasNeighbor(self, currentNode):"""判断currentNode在图中是否有未访问过的邻居节点:param currentNode: 需要判断的节点:return: 未访问过的邻居列表"""all_neighbors = list(self.G.neighbors(currentNode))not_visited_neighbors = []for node in all_neighbors:# 判断一下邻居节点是否已经在游走的路径上if(node not in self.RW):not_visited_neighbors.append(node)return not_visited_neighborsdef randomSelectFromCom(self):# 从当前社区中随机选择一个节点available_nodes = []for node in self.Com:if (node not in self.RW):available_nodes.append(node)return available_nodes[int(random.random() * len(available_nodes))]def walk(self):self.initialize()dont_visited_node = []while len(self.RW) < self.l:currentNode = self.RW[len(self.RW) - 1]neighbors = self.hasNeighbor(currentNode)if len(neighbors) > 0:if(random.random() < self.alpha):# select vj at random from vi's neighborsnode = neighbors[int(random.random() * len(neighbors))]else:# select vj at random from members of vi's communitiesnode = self.randomSelectFromCom()if node not in dont_visited_node:self.RW.append(node)else:# backtrack in the path and select the last node which has neighbors that are not in the path# 回溯到上一个节点，再进行判断if len(self.RW) > 1:self.RW.remove(self.RW[len(self.RW) - 1])dont_visited_node.append(self.RW[len(self.RW) - 1])# 返回路径return self.RW
测试所用数据集：Zachary’s karate club
数据集可视化：
测试方法：
from gensim.models import word2vec
import networkx as nx
import CommunityawareRWfilename = "a.txt"# 在图上进行随机游走，生成用于输入skip-gram的语料库
def communityawarerw():G = nx.karate_club_graph()for i in range(30):for node in G.node:# 暂定随机游走的窗口长度为6，游走阈值为0.2，且所有节点在一个社区中resu = CommunityawareRW.RandomWalk(G, node, G.nodes, 6, 0.2).walk()with open(filename, encoding="utf-8", mode="a+") as f:for node in resu:f.write(str(node) + " ")f.write("\r\n")communityawarerw()# 加载生成的语料库，输入到skipgram模型中，用于计算K相似
def generate():sentences = word2vec.LineSentence(filename)model = word2vec.Word2Vec(sentences, hs=1,min_count=1,window=3,size=100)# model.save('text.model') 模型可保存# model1 = word2vec.load('text8.model') 模型可加载resu = dict()for i in range(34):req_count = 3for key in model.wv.similar_by_word(str(i), topn=100):if req_count > 0:if resu.get(key[0]) == None:resu[key[0]] = 1else:resu[key[0]] += 1req_count -= 1return resuresu = generate()# 排序结果字典
print(sorted(resu.items(), key=lambda x:x[1], reverse=True))
经过多次测试，发现34、1等中心性比较高的节点会比较频繁的被捕捉到，感觉是合理的。因为网络比较小，就采用直观的“看、感觉”的方式。