networkx-60
刘耀文的大沙雕
钟意阿满
图计算引擎Neo4j和Graphscope有什么区别？
近年来，全球大数据进入加速发展时期，数据量呈现指数级爆发式增长，而这些大量数据中不同个体间交互产生的数据以图的形式表现，如何高效地处理这些图数据成为了业界及其关心的问题。很过用普通关系数据无法跑出来的结果，用图数据进行关联分析会显得异常高效。
提到处理图数据，我们首先想到NetworkX，这是网络计算上常用的Python包，可提供灵活的图构建、分析功能。但是我们使用NetworkX跑大规模图数据时，不仅经常碰到内存不足的问题，而且分析速度很慢，究其原因，是NetworkX只支持单机运行。通过网上搜索，新发现了一个名为GraphScope的系统不仅号称兼容NetworkX的API，而且支持分布式部署运行，性能更优。针对GraphScope和NetworkX的处理能力，我们参考图计算中常用的测试框架LDBC，通过一组实验来对比下二者的性能。
一、实验介绍
为了比较两者的计算效率，先用阿里云拉起了配置为8核CPU，32GB内存的四台ECS，设计了三组比较实验，分别是NetworkX单机下的计算性能，GraphScope单机多worker的计算性能以及GraphScope分布式多机多worer的计算性能。
数据上，我们选取了SNAP开源的图数据集twitter，来自 LDBC数据集的datagen-7_5-fb,datagen-7_7-zf和datagen-8_0-fb作为实验数据，以下是数据集的基本信息：
· Twitter: 81,307个顶点，1,768,135条边。
· Datagen-7_5-fb： 633,432个顶点，34,185,747条边，稠密图。
· Datagen-7_7-zf： 13,180,508个顶点，32,791,267条边，稀疏图。
· Datagen-8_0-fb： 1,706,561个顶点，107,507,376条边，这个数据集主要测试两个系统可处理的图规模能力。
实验设计上我选择常用的SSSP、BFS、PageRank、WCC算法，以及较高复杂度的All Pair shortest Path length算法，以载图时间，内存占用和计算时间这三个指标为依据，对两个系统进行计算性能的比较。
NetworkX是一个单机系统，在实验中只考虑NetworkX在单机环境下的运行时间；GraphScope支持分布式运行，故进行两个配置，一个是单机4worker，另外一个配置是4台机器，每台机器4个worker。
二、实验结果
首先，GraphScope的载图速度比NetworkX显著提升。
在前三个图数据集中，无论是GraphScope的单机多worker模式，还是GraphScope的分布式模式，载图速度都比NetworkX快：
GraphScope单机模式载图速度平均比NetworkX快5倍，最高纪录——在datagen-7_5-fb上比NetworkX快了6倍。
分布式模式下GraphScope的载图时间比NetworkX平均快了27倍，最高纪录——在datagen-7_7-zf数据集上比NetworkX快了63倍。
在datagen-8_0-fb数据集上，NetworkX因内存溢出无法载图，GraphScope单机多worker和GraphScope分布式载图时间分别为142秒和13.6秒。
表一：载图时间对比
载图时间
NetworkX
GraphScope单机
GraphScope分布式
11.2
3.1
1.8
datagen-7_5-fb
256
45.6
36.6
datagen-7_7-zf
316
71.3
50
datagen-8_0-fb
OOM
142
13.6
其次，GraphScope的内存使用效率比NetworkX显著提升。
在datagen-8_0-fb数据集上，NetworkX在32G的内存上无法载完图，而GraphScope仅需要24G的内存即可载入在datagen-8_0-fb数据集。
表二：内存占用对比
内存占用
NetworkX
GraphScope
datagen-7_5-fb
14G
6G
datagen-7_7-zf
28G
18G
datagen-8_0-fb
OOM
24G
再次，GraphScope的计算速度比NetworkX显著提升。
SSSP算法上，GraphScope单机多worker模式平均要比NetworkX快22倍，最快在datagen-7_7-zf数据集上快了32倍。GraphScope分布式模式下平均要比NetworkX快103倍，最快datagen-7_5-fb数据集上快了182倍。
表三： SSSP计算时间对比（单位：秒）
SSSP
NetworkX
GraphScope单机
GraphScope分布式
2.45
1.32
0.28
datagen-7_5-fb
37.9
1.21
0.31
datagen-7_7-zf
5.84
0.18
0.03
datagen-8_0-fb
OOM
2.76
0.82
BFS算法上，GraphScope单机多worker模式平均要比NetworkX快13倍，最快datagen-7_5-fb数据集上快了22倍。GraphScope分布式模式下平均要比NetworkX快16倍，最快在datagen-7_5-fb数据集上快了28倍。
表四： BFS计算时间对比（单位：秒）
BFS
NetworkX
GraphScope单机
GraphScope分布式
1.53
0.16
0.17
datagen-7_5-fb
44.68
2.52
1.56
datagen-7_7-zf
7.98
0.75
0.72
datagen-8_0-fb
OOM
11.02
5.73
PageRank算法上，GraphScope单机多worker模式平均要比NetworkX快62倍，最快twitter数据集上快了80倍。GraphScope分布式模式下平均要比NetworkX快65倍，最快在twitter数据集上快了71倍。
另外，PageRank计算过程中，NetworkX在datagen-7_7-zf上内存溢出，没有完成计算，GraphScope单机多worker模式和分布式模式计算时间分别为25秒和22秒；
表五：PageRank计算时间对比（单位：秒）
PageRank
NetworkX
GraphScope单机
GraphScope分布式
24.01
0.37
0.33
datagen-7_5-fb
300
6.73
5.17
datagen-7_7-zf
OOM
19.31
7.79
datagen-8_0-fb
OOM
24.96
21.88
WCC算法上，GraphScope单机多worker模式平均要比NetworkX快44倍，最快在datagen-7_7-zf数据集上快了104倍。GraphScope分布式模式下平均要比NetworkX快76倍，最快datagen-7_5-fb数据集上快了194倍。
表六： WCC计算时间对比（单位：秒）
WCC
NetworkX
GraphScope单机
GraphScope分布式
0.6392
0.0296
0.0233
datagen-7_5-fb
26.03
0.25
0.13
datagen-7_7-zf
83.19
14.57
12.98
datagen-8_0-fb
OOM
0.34
0.4991
在复杂度极高的All pair shortest path length算法上，NetworkX在twitter图上即内存溢出，无法计算。GraphScope在分布式模式下完成了twitter图的All pair shortest path length计算，耗时76分钟。
表七： All Pair Shortest Path Length（单位：秒）
APSP
NetworkX
GraphScope单机
GraphScope分布式
OOM
OOM
4575.87
三、总结
从实验结果可以看到，在同等条件下，无论在载图时间、内存占用和计算时间上，GraphScope都要大大优于NetworkX，性能优化可以达到几十倍甚至上百倍。
6979阿强
关注
@网络算法工具 networkX igraph 的性能问题。
alston_ethannical的博客。
24
@网络算法工具 networkX igraph 的性能问题 问题的提出 当我用 50万数据去跑 networkX 开发出来的算法时，遇到了一个计算性能的问题,这个问题时很慢。 寻找答案 发现 networkX再性能方面比较差。当节点上万，边上十万的时候，新能慢的问题就会显现出来 为了解决图算法问题，该怎么办呢 遇到问题，首先定义问题的边界。也就是 先找到限制问题的条件。然后缩小问题范围。我要解决的问题是：在解决图算法相关的问题时，如何能够快速计算出结果。但是目前的算法时用networks实现的。问题的根源是。
开源！一文了解阿里一站式图计算平台GraphScope。
阿里云开发者
2767
简介：随着大数据的爆发，图数据的应用规模不断增长，现有的图计算系统仍然存在一定的局限。阿里巴巴拥有全球最大的商品知识图谱，在丰富的图场景和真实应用的驱动下，阿里巴巴达摩院智能计算实验室研发并开源了全球首个一站式超大规模分布式图计算平台GraphScope，并入选中国科学技术协会“科创中国”平台。本文详解图计算的原理和应用及GraphScope的架构设计。一 什么是图计算图数据对一组对象（顶点）及其关系（边）进行建模，可以直观、自然地表示现实世界中各种实体对象以及它们之间的关系。在大数据场景下，社交网络、交。
一文了解阿里一站式图计算平台GraphScope_阿里云云栖号。
10-2
GraphScope 提供了各类常用的分析算法,包括连通性计算类、社区发现类和 PageRank、中心度等数值计算类的算法,后续会不断扩展算法包,在超大规模图上提供与 NetworkX 算法库兼容的分析能力。此外也提供了丰富的图学习算法包,内置支持 Graph...。
5大典型模型测试单机训练速度超对标框架,飞桨如何做到...。
10-28
导读:飞桨(PaddlePaddle)致力于让深度学习技术的创新与应用更简单。在单机训练速度方面,通过高并行、低开销的异步执行策略和高效率的核心算子,优化静态图训练性能,在Paddle Fluid v1.5.0的基准测试中,在7个典型模型上进行了测试(图像领域...。
强化学习经典算法笔记(六)：深度Q值网络 Deep Q Network。
hhy_csdn的博客
9093
前期回顾 强化学习经典算法笔记(零)：贝尔曼方程的推导 强化学习经典算法笔记(一)：价值迭代算法Value Iteration 强化学习经典算法笔记(二)：策略迭代算法Policy Iteration 强化学习经典算法笔记(三)：蒙特卡罗方法Monte Calo Method 强化学习经典算法笔记(四)：时间差分算法Temporal Difference（Q-Learning算法） 强化学习经典算...。
GraphX和GraphFrame connectedComponent计算性能对比。
高臭臭的博客
3046
测试文件：用Graph rmatGraph 1000000 2000000 去重后 494587个点，1997743个边 运行环境：三台服务器，246 GB，core 71. 测试三个运行例子1：Graph connectedComponents 2：GraphFrame connectedComponents 3：GraphFrame connectedComponents setAlgor。
...network、伪代码、算法理解、代码实现、tensorboard...。
11-3
定义一个q_network函数来构建Q network,输入游戏状态Q network并得到对所有动作的Q值。 网络构成给为三个带有池化的卷积层和一个全连接层。 tf.reset_default_graph()defq_network(X,name_scope):# Initialize layersinitializer=tf....。
【读书笔记】【机器学习实战】第十一章：训练深度神经网络。
MJ_Lee的博客
612
阅读书籍为《Hands-On Machine Learning with Scikit-Learn & TensorFlow》王静源等翻译的中文译版《机器学习实战，基于 Scikit-Learn 和 TensorFlow》,本文中所有图片均来自于书籍相关部分截图。 本章介绍了DNN训练过程中三个常见问题，并依次给出解决方案。 章节的最后还给出当不知道如何DNN训练时一些属性可以选的比较好的...。
Networkx 计算网络效率。
tengqingyong的博客。
5860
本人在计算网络效率的时候遇到了一个问题 networkx 提供了最短路径函数shortest_path及shorest_path_length 我在计算网络效率构造了一个无向图，但是我在计算点与点之间的最短路径长度时总是提示我说点不存在图中， 我在上面使用nx.average_shortest_path_length(UG)的时候可以得到网络平均最短路径长度；这个说明我的点都...。
Pandas/networkx图分析简单入门。
weixin_34306676的博客。
516
对于图论而言，大家或多或少有些了解，数学专业或计算机相关专业的读者可能对其更加清楚。图论中的图像是由若干给定的点及连接两点的线所构成的图形，这样的图像通常用来描述某些事物之间的某种特定关系，用点代表事物，用两点之间的连接线表示二者具有的某种关系，在互联网与通信行业中应用广泛。图论分析（Graph analysis）并不是数据科学领域中的新分...。
networkx--四种网络模型。
weixin_30764883的博客。
380
NetworkX提供了4种常见网络的建模方法，分别是：规则图，ER随机图，WS小世界网络和BA无标度网络。 一. 规则图 规则图差不多是最没有复杂性的一类图，random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点，每个节点有d个邻居节点的规则图。 下面一段示例代码，生成了包含20个节点、每个节点有3个邻居的规则...。
igraph/networkx学习笔记之…
nuoline的专栏
1万+
原文地址：—— 数据结构">igraph/networkx学习笔记之一 —— 数据结构作者：zhengw789 首先，基本上所有的graph library都有其局限性，不同的数据结构有优点的同时必然有缺点，图算法对数据结构的依赖性构成另一个原因。所以如果是想用一个工具包解决所有的问题显然是一种奢望，很多时候甚至必须要从头写自己的代码。但是阅读igraph和networkx这样成型了的函数库对熟悉。
python下的复杂网络编程包networkx的使用（摘抄）
weixin_30631587的博客。
2335
原文：http://blog.sciencenet.cn/home.php?mod=space&uid=404069&do=blog&classid=141080&view=me&from=space 复杂网络分析库NetworkX学习笔记（1）：入门 NetworkX是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网...。
更快更简单|飞桨PaddlePaddle单机训练速度优化最佳实践。
PaddlePaddle
1672
导读：飞桨（PaddlePaddle）致力于让深度学习技术的创新与应用更简单。在单机训练速度方面，通过高并行、低开销的异步执行策略和高效率的核心算子，优化静态图训练性能，...。
GraphX与GraphLab、Pregel的对比。
yang灬仔
588
分布式批同步BSP Pregel、GraphLab、GraphX都是基于BSP（Bulk Synchronous Parallel）模式，即整体同步并行。一次计算过程由一系列全局超步组成，每一个超步由并发计算、通信和同步三个步骤组成。从垂直上看,一个程序由一系列串行的超步组成。从水平上看，在一个超步中，所有的进程并行执行局部计算。BSP最大的好处是编程简单，但在某些情况下BSP运算的性能非常差，...。
TensorFlow学习记录：VGGNet卷积神经网络模型。
weixin_41137655的博客。
308
1.VGGNet模型结构简介 VGGNet是由牛津大学计算机视觉几何组（Visual Geomety Group,VGG）和Google Deepmind公司的研究员合作研发的深度卷积神经网络，VGG的成员Karen Simonyan和Andrew Zisserman在2014年撰写的论文《Very Deep Convolutional Networks for Large-Scale Image...。
11月编程语言排行冠军揭晓，稳。
热门推荐
IT教育任姐姐的博客
4万+
大家好 今天任姐姐要跟小伙伴们分享 2021年11月最新TIOBE指数 11月编程排行榜 Python继续榜首 本月的幸运儿只有一个，那就是Python！ 继上个月我们见证了Python夺冠这一历史性的画面之后，这个月Python仍旧稳坐榜首，看来Python这股大风还在继续刮。 随后分别是 C、Java、C++、C#，这些也都是我们的老朋友了。 PHP即将跌出前十 自20多年前TIOBE 指数开始发布以来，PHP 一直常驻在榜单前十，然而最近，该语言已经开始在前十。
python能做什么软件？Python到底能干嘛，一文看懂。
小分享
6573
Python培训有哪些内容?很多零基础学员不知道Python软件是干什么用的?Python软件是Python工程师编写代码时所需要的编辑工具,现在比较常用的Python软件有Visu... 那么在选择Python培训机构时学生尤为关注的就是培训内容,从现在几家大的机构可以看出,Python培训主要学习第一阶段Python核心编程(Pyth... 一文读懂Python内置变量,函数,模块在这里解释下什么是解释性语言什么是编译性语言: 编译性语言:如c++,c等,写好的代码要通过编译器编译成操作系统直接可。
Django中超级用户的创建和删除操作。
最新发布
Protinx的博客
91
创建超级用户 这就很easy了，毕竟这是所有初学者都会的，操作如下： 打开Terminal，输入： python manage.py createsuperuser 然后按照提示输入相应的用户名、邮箱和密码就可以啦，如下： 创建超级用户 可以看到上面我的密码输入了三次，还有不成功的提示，Django本身对于超级用户的密码要求还是很多的，大家定义密码要注意啊，或者如果只是自己学习的话，也可在‘Bypass password validation and create user an.。
上海python培训中心
weixin_63757190的博客。
166
前几天，有个读者在后台留言，说： “最近被论文折磨得快崩溃了，我现在是恨不得克隆十个自己，一个呆在科室值班，一个去写月底要送审的稿子，一个去上百个网站翻数据..... 还有另外七个“我”，这边六七篇论文还没搞定。那边又有新论文要开题了，加上最后一个“本我”，刚刚够用，我可真是个数学天才！ 可现实是只有一个我，只能天天熬夜。 好家伙，整得我都开始反问自己，是不是只有我的科研生活这么兵荒马乱？” 其实他不是个例，成千上万的科研人都要面对无尽的实验分析、反复修改的论文。 难道就只有被虐的份吗？
python装饰器
Live&Learn的博客。
1208
学习目标：一口气把装饰器描述清楚 弄清楚装饰器前要理解三个东西： 函数对象、函数嵌套、函数构成闭包。 学习内容： 函数对象好说，python编程语言属于动态语言，python中一切皆对象，所以函数也是对象。 函数对象用函数名称表示（仅名称，没有括号，也没有参数）。 例如，定义了一个求和函数add，那么此处的add就是个函数对象。 def add(username, a, b): print(f"{a}+{b}={a + b}") return a + b 函数嵌套或者嵌套函数，就是定。
©️2021 CSDN 皮肤主题: 游动-白 设计师:白松林 返回首页。
关于我们
招贤纳士
广告服务
开发助手
400-660-0108
kefu@csdn.net
在线客服
工作时间 8:30-22:00。
公安备案号11010502030143。
京ICP备19004658号
京网文〔2020〕1039-165号。
经营性网站备案信息
北京互联网违法和不良信息举报中心。
网络110报警服务
中国互联网举报中心
家长监护
Chrome商店下载
©1999-2021北京创新乐知网络技术有限公司。
版权与免责声明
版权申诉
出版物许可证
营业执照
6979阿强
码龄0年
暂无认证
11
原创
13万+
周排名
12万+
总排名
579
访问
等级
132
积分
粉丝
获赞
评论
收藏
私信
关注
热门文章
GraphScope、Neo4j与TigerGraph单机环境下性能对比 146。
NetworkX与GraphScope的性能对比 88。
GraphScope、Gemini与GraphX的性能对比 60。
分布式图计算引擎 46
国足历届世界杯对战图关系 45。
最新评论
图分析入门
大家一起学编程（python）: 感谢博主的分享！
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
最新文章
2021-10-11
图数据库在社交方向上的应用
国足历届世界杯对战图关系
2021年11篇
你的浏览器目前处于缩放状态，页面可能会出现错位现象，建议100%大小显示。
举报
————————————————
版权声明：本文为CSDN博主「6979阿强」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/tanekf6979/article/details/120067176。
抱起亚轩找小葵
Python中数据可视化经典库有哪些？
Neo4j是单机系统，主要做图数据库。GraphScope是由阿里巴巴达摩院智能计算实验室研发的图计算平台，是全球首个一站式超大规模分布式图计算平台，并且还入选了中 国科学技术协会“科创中 国”平台。Graphscope的代码在github.com/alibaba/graphscope上开源。SSSP算法上,GraphScope单机模式下平均要比Neo4j快176.38倍，最快在datagen-9.2_zf数据集上快了292.2倍。
大圣杰锅是
如何利用python 的 networkx从文件中读数据加节点和边
Python有很多经典的数据可视化库，比较经典的数据可视化库有下面几个。
matplotlib
是Python编程语言及其数值数学扩展包 NumPy 的可视化操作界面。它利用通用的图形用户界面工具包，如 Tkinter, wxPython, Qt 或 GTK+，向应用程序嵌入式绘图提供了应用程序接口。
pyplot 是 matplotlib 的一个模块，它提供了一个类似 MATLAB 的接口。 matplotlib 被设计得用起来像 MATLAB，具有使用 Python 的能力。
优点：绘图质量高，可绘制出版物质量级别的图形。代码够简单，易于理解和扩展，使绘图变得轻松，通过Matplotlib可以很轻松地画一些或简单或复杂的图形，几行代码即可生成直方图、条形图、散点图、密度图等等，最重要的是免费和开源。
pandas
Pandas 是一个开放源码、BSD 许可的库，提供高性能、易于使用的数据结构和数据分析工具。Pandas 广泛应用在学术、金融、统计学等各个数据分析领域。需要说明的是它不是“熊猫”，名字衍生自术语 "panel data"（面板数据）和 "Python data analysis"（Python 数据分析）。
优点：是Python的核心数据分析支持库，提供了快速、灵活、明确的数据结构，旨在简单、直观的处理关系型、标记型数据。对于数据分析专业人士，它是数据分析及可视化的利器。
seaborn
Seaborn是基于matplotlib的图形可视化python包。它提供了一种高度交互式界面，便于用户能够做出各种有吸引力的统计图表。
它是基于matplotlib更高级的API封装，从而使得作图更加容易，在大多数情况下使用seaborn能做出很具有吸引力的图，应该把Seaborn视为matplotlib的补充，而不是替代物，它能高度兼容numpy与pandas数据结构以及scipy与statsmodels等统计模式。
优点：matplotlib高度封装，代码量少，图表漂亮。比起matplotlib具有更美观、更现代的调色板设计等优点。scikit-plot。
这是一个跟机器学习有效结合的绘图库。想要深入学习的小伙伴参见其github仓库，这里不再赘述了。
优点：Scikit-Plot是由ReiichiroNakano创建的用在机器学习的可视化工具，能最快速简洁的画出用Matplotlib要写很多行语句才能画出的图。关键是对于机器学习相关可视化处理，该库有较好的支持。
Networkx
networkx是Python的一个包，用于构建和操作复杂的图结构，提供分析图的算法。图是由顶点、边和可选的属性构成的数据结构，顶点表示数据，边是由两个顶点唯一确定的，表示两个顶点之间的关系。顶点和边也可以拥有更多的属性，以存储更多的信息。
优点：用于创建、操纵和研究复杂网络的结构、以及学习复杂网络的结构、功能及其动力学。
上面是我的回答，希望对您有所帮助！
小韩在追星
如何用python实现《多社交网络的影响力最大化问题分析》中的算法
如何利用python 的 networkx从文件中读数据加节点和边。
译Python之前您最好先安装一系列的开发工具和一些拓展库，虽然不是必须的，但这样Python才能依赖这些工具和拓展库展示它强悍的功能。下面是利。
用yum进行工具和拓展库安装的示例命令，直接copy执行即可（注意部分命令显示不全，但可以通过移动光标查看和复制）。
yumgroupinstall"Development tools"。
yuminstallzlib-develbzip2-developenssl-develncurses-develsqlite-develreadline-develtk-develgdbm-develdb4-devellibpcap-develxz-devel。
该考虑的因素
在您编译和安装Python之前，有些东西您是应该知道或考虑的。如下。
Unicode编码
Python
编码问题历史悠久，但不用过多关注，知道它目前支持Unicode编码即可（Python3中默认的）。考虑到兼容性等原因，除非有特殊的理由，您最好配。
置下Python 3.2和更早的版本，使其支持UTF-32编码，虽然会增加小小的内存代价。
小韩在追星
怎样基于python networkx实现社区发现
经过一周，现已初步完成，其中多出代码不够美观以及效率不高，还请指点。
# _*_ coding:utf-8 _*_。
# ==================================================================================。
# Description: Influence Maximization on Multiple Social Networks。
# ==================================================================================。
import matplotlib.pyplot as plt 。
import networkx as nx。
import heapq
#总图
G = nx.DiGraph()。
def load_graph(file):。
'''
加载文件为列表格式,并得到G,画出图结构。
'''
#将总列表设成全局格式
global gllist
#迭代文件中每个元素
with open(file) as f:。
lines = f.readlines()。
mylist = [line.strip().split() for line in lines]。
gllist = []
#将字符串型转换为整型
for i in mylist:。
gllist.append(i[:-2]+map(lambda x: float(x), i[-2:]))。
print '初始全局列表:'。
print gllist
drawlist=[]
#提取二维列表mylist每行前三个元素,赋给新的列表drawlist。
for i in range(len(mylist)):。
drawlist.append([])。
for j in range(3):。
drawlist[i].append(mylist[i][j])。
#将列表drawlist加载为有向加权图。
G.add_weighted_edges_from(drawlist)。
nx.draw(G, with_labels=True, width=1, node_color='y', edge_color='b')。
plt.show()
print 'G图中所有节点:',G.nodes()。
print 'G图中所有边:',G.edges()。
print '\n'
def get_self_node(gllist, target=None):。
'''
获取目标节点的自传播节点,返回selflist并包含目标节点。
'''
#初始化自传播节点列表
selflist = [target]。
#存放已传播节点列表
haslist = []
flag = 0
while (flag != 0):。
flag = 0
for target in selflist:。
if target not in haslist:。
for i in range(len(gllist)):。
#判断二维列表中,每行第三个元素是否为1,若为1，则为自传播节点。
if ((gllist[i][0] == target)or(gllist[i][1]==target))and(gllist[i][3]==1.0):。
if gllist[i][0] == target:。
if gllist[i][1] not in haslist:。
selflist.append(gllist[i][1])。
haslist.append(gllist[i][1])。
flag += 1
else:
if gllist[i][0] not in haslist:。
selflist.append(gllist[i][0])。
haslist.append(gllist[i][0])。
flag += 1
#去除重复元素
haslist = set(haslist)。
selflist = set(selflist) 。
#去除重复元素
selflist = set(selflist)。
return selflist。
def longest_path(gllist,source=None,target=None):。
'''
获取起始点到实体的最大路径集合,返回为longestpath列表。
'''
longestpath = []。
newlist = []
for i in range(len(gllist)):。
newlist.append([])。
for j in range(3):。
newlist[i].append(gllist[i][j])。
#构建图结构
G1 = nx.DiGraph()。
#添加带权有向边
G1.add_weighted_edges_from(newlist)。
#获取目标节点的所有自传播街边,并存入selflist中。
selflist = get_self_node(gllist, target)。
max_path = 0
val_path = 1
#获取初始节点到目标节点及目标节点的自传播节点的最大路径。
for v in selflist:。
if v != source:。
#遍历两点之间所有路径,并进行比对。
for path in nx.all_simple_paths(G1,source=source,target=v):。
#判断路径后两个元素是否为相同实体（如：b1->b2）
if is_self_transmit_node(path[-2], v) == 0:。
for i in range(0, len(path)-1):。
val_path *= G1.get_edge_data(path[i], path[i+1])['weight']。
if max_path < val_path:。
max_path = val_path。
val_path = 1
#若目标节点为起始节点则直接跳出。
else: continue ############ 有待商榷 ##############。
longestpath.append(max_path)。
#返回初始节点到实体的最大路径。
return longestpath。
def is_self_transmit_node(u, v):。
'''
判断目标节点不为起始节点的自传播点。
'''
flag = 0
#获得起始节点的所有自传播点
selflist = get_self_node(gllist, v)。
for x in selflist:。
if u == x:
flag = 1
return flag
def single_strong_infl(longestpath):。
'''
计算起始点到实体的传播概率（影响强度）,返回影响强度stronginfl。
'''
temp = 1
for x in longestpath:。
temp *= 1-x
stronginfl = 1-temp。
return stronginfl。
def all_strong_infl(G):。
'''
获得每个节点对实体的影响概率
'''
allstrong = [] #初始化所有节点的加权影响范围列表。
gnodes = [] #初始化节点列表。
tempnodes = [] #初始化临时节点列表。
gnodes = G.nodes()。
for u in gnodes:。
strong = 0 #存储初始节点对每个实体的影响范围加权，初始化为0。
#重置临时节点列表
tempnodes = G.nodes()。
for v in tempnodes:。
#非自身节点
if u != v:
#判断目标节点不为起始节点的自传播点。
if is_self_transmit_node(v, u) == 0:。
#获取起始节点到实体间最大加权路径，并存入longestpath。
longestpath = longest_path(gllist, u, v)。
#去除已遍历目标节点的所有自传播节点。
renode = get_self_node(gllist, v)。
for x in renode:。
if x != v:
tempnodes.remove(x)。
#计算起始节点到实体间传播概率（影响强度）
stronginfl = single_strong_infl(longestpath)。
strong += stronginfl 。
#添加单个节点到所有实体的加权影响范围。
allstrong.append([u, round(strong, 2)])。
#返回每个节点到所有实体的加权影响范围。
return allstrong。
#output allstrong : [['a1', 2.48], ['a2', 1.6880000000000002], ['b1', 0.7], ['b2', 0], ['c1', 0], ['d2', 0.6]]。
def uS_e_uppergain(u, ev, S):。
'''
获取节点u在集合S的基础上对实体ev的影响增益, 传入候选节点,上界gain(u|S, ev)。
'''
#获取目前实体的所有自传播节点。
selflist = get_self_node(gllist, ev)。
stronglist = []。
#遍历自传遍节点
for v in selflist:。
'''
判断节点v是否存在种子集合S中。
其中v为单个节点,如v(ev, Gi)。
S为种子节点集合,如['a1','a2','b1','b2','c1','d2']。
'''
if v in S:
ppSv = 1
else:
longestpath = []。
#遍历种子集合
for s in S:
#初始化路径权值与最大路径权值。
val_path = 1
max_path = 0
#遍历两点之间所有路径，并进行比对。
for path in nx.all_simple_paths(G,source=s,target=v):。
#判断路径后两个元素是否为相同实体（如：b1->b2）
if is_self_transmit_node(path[-2], v) == 0:。
for i in range(0, len(path)-1):。
val_path *= G.get_edge_data(path[i], path[i+1])['weight']。
if max_path < val_path:。
max_path = val_path。
#重置路径权值为1
val_path = 1
#将最大加权路径存入longestpath列表。
longestpath.append(max_path)。
#得到上界pp(S,v)的影响概率,上界pp(S,v)。
ppSv = single_strong_infl(longestpath)。
stronglist.append(ppSv)。
#得到上界pp(S,ev)的影响概率,上界pp(S,ev)。
ppSev = single_strong_infl(stronglist)。
#获取pp(u,ev)
ppuev = single_strong_infl(longest_path(gllist, u, ev))。
#计算上界gain(u|S，ev)。
uSevgain = (1 - ppSev) * ppuev。
return uSevgain。
def uppergain(u, emu, ems, S):。
'''
在已有种子集合S的基础上,求得节点u的影响增益上界,。
其中传进参数ems为二维列表,如[['a1',2.48],['a2',1.688]],S则为['a1','a2']。
'''
uSgain = 0.0
#遍历emu得到列表形式,得到如['a1',2.48]形式。
for ev in emu:
#判断节点是否存在种子集合中
if ev[0] in S:
uSgain += uS_e_uppergain(u, ev[0], S)。
else:
uSgain += ev[1] 。
#返回上界gain(u|S)
return uSgain
def bound_base_imms(G, k):。
'''
完全使用影响增益上界的方式选择top-k个种子节点的过程。
'''
#初始化emu,H,初始化ems=空集,S=空集 。
Htemp = []
Htemp = all_strong_infl(G)。
H = []
#遍历Htemp=[['a1',2.48],['a2',1.688]],得到如['a1',2.48]形式。
for x in Htemp:。
#逐个获取二维列表中每一行，形式为['a1',2.48,0]。
H.append([x[0],x[1],0])。
emu = []
emu = all_strong_infl(G)。
ems = []
S = []
for i in range(k):。
#提取堆顶元素,tnode的形式为['a1',2.48,0]。
tnode = heapq.nlargest(1, H, key=lambda x: x[1])。
#将[['b2', 3.1, 0]]格式改为['b2', 3.1, 0]格式。
tnode = sum(tnode, [])。
while (tnode[2] != i):。
gain = 0.0
#获取节点u的影响增益上界
gain = uppergain(tnode, emu, ems, S)。
#赋值影响范围
tnode[1] = gain。
#修改status
tnode[2] = i
#对堆进行排序
H = heapq.nlargest(len(H), H, key=lambda x: x[1])。
#获取堆顶元素
tnode = heapq.nlargest(1, H, key=lambda x: x[1])。
tnode = sum(tnode, [])。
#添加node到种子集合
S.append([tnode[0]])。
#更新ems,添加新节点及节点对每个实体的影响范围加权。
ems.append([tnode[0], tnode[1]])。
#删除堆顶元素
H.remove(tnode)。
print ems
return sum(S, [])。
if __name__=='__main__':。
#大小为k的种子集合S
k = 60
#加载文件数据,得到图G和初始列表gllist。
load_graph('test.txt')。
#完全使用影响增益上界值的计算过程函数,打印种子集合S。
print '种子集合:',bound_base_imms(G, k)。
test.txt
a1 b1 0.2 0
a1 c1 0.8 0
a2 b2 0.4 0
a2 d2 1 0
b1 c1 0.7 0
c2 a2 0.8 0
d2 b2 0.6 0
a1 a2 1 1
a2 a1 0.1 1
....
a1 l1 0.5 0
a1 m1 0.5 0
a1 q1 0.5 0
a1 v1 0.5 0
a1 z1 0.5 0
a1 s1 0.5 0
a1 w1 0.5 0
a1 u1 0.5 0
其中前两列为传播实体，第三列为实体间传播概率，最后一列为0代表同一网络传播，为1代表网络间自传播。
下来要进行优化：
1.采用独立级联模型，设置阈值。
2.将最大路径改为最短路径，利用log。