Python图算法系列9图的应用探索

说明

假设我们拿到了一批数据（已经存储在neo4j中），如何通过图的方式实现其价值呢？

• 实现价值的途径
  + 1 事实性质的查询
  + 2 模式的查询与目标问题的关联（强规则）
  + 3 模式查询的结果进行模糊描述（弱规则-聚类）
  + 4 模式查询的结果进行精确描述（弱规则-分类）

事实性质的查询。数据库本身的价值就是查询，所以建立了某种图库（或者说关系库）之后，那么第一个应用就是查事实。例如xx查、xx宝，在有了大量的股权关系后，你就可以查感兴趣的目标。但是这种价值一般来说附加值相对低，属于寡头垄断的行业，没什么意思。

模式的查询与目标问题的关联（强规则）。在这个简单查数据的基础之上，进行一些带有特定模式的

• 需要考虑的问题
  + 1 多种关系（关联）的使用。如果一个节点存在多种关系，用哪种关系来解决哪种问题呢？还是糅合起来？
  + 2 数据太大怎么办？如果库中不是数万个节点，而是数千万，无法读入内存怎么办？
  + 3 怎样建立图的关系才是正确的(虚边与实边)？

0 图的重新构造

关于图的边计算方法有很多种，可以参考社交网络中的Link Prediction, 文章主要是参考What will Facebook friendships look like tomorrow?这篇文章的。
里面有些概念这里罗列一下：

1. 图距离 Graph Distance ：一个最直接的预测方法就是计算两个结点间的距离，然后根据距离的大小来预测，两个结点越近那么就越容易在未来建立联系。
2. 指数衰减距离 Katz (Exponentially Damped Path Counts)：我们还可以考虑用x，y之间存在的路径的数量来衡量它们的距离。然而，路径有长有短，一般认为，那些很长的路径其实是没什么说服力的，于是引入指数衰减机制随着路径长度进行衰减。
3. 命中时间(Hitting Time)从x出发，在附近随机的跳转，如果到达y，则记录下这次到达y的所需跳转次数。最后我们用 总跳转次数/到达y的次数 来表示距离。
4. 模拟PageRank(Rooted PageRank)如果y是一个非常有影响力的人，那么很多人都能在非常少的跳转次数下到达y，为了减轻这效应，我们增加一个随机”reset”以及继续游走的机制。【这个MCMC非常相似】
5. 共有邻居(Common Neighbors)当两个用户有着很多个相同的邻居，我们就认为这两个用户很有可能建立联系。
6. 杰卡德相关(Jaccard’s Coefficient)然而Common Neighbors有一个很大的问题，假设有一个人有非常多的邻居，那么所有人都会倾向于预测跟他产生互动，为此，我们还要把他们邻居的数量考虑进去，于是我们认为，如果两个人共同邻居的数量在他们所有好友数量中占比越大，就认为可能建立联系。
7. 频率权重的共同邻居(Adamic/Adar ,Frequency-Weighted Common Neighbors)。这个方法同样是对Common Neighbors的改进，当我们计算两个相同邻居的数量的时候，其实每个邻居的“重要程度”都是不一样的，我们认为这个邻居的邻居数量越少，就越凸显它作为“中间人”的重要性，毕竟一共只认识那么少人，却恰好是x，y的好朋友。
8. 朋友的朋友测度(Friendes-mearsure)既然两个人有相同的好友可以表达他们间的距离，那么我们可以把这一个思想推广，我们认为，他们的好友之间很有可能互为好友。我们就计算他们好友之间互为好友的数量作为评价标准。
9. 偏好联系（Preferential Attachment）如果两个用户拥有的好友数量越多，那么就越有可能更愿意去建立联系。也就是“富人越富”原则，基于这思想,用他们两个用户的好友数量的乘积作为评分。

0.1 直接距离

上面的1~4类关系属于直接距离，所以我们构建图的时候不是使用原始的数据(例如A-Invest->B),而是通过一些方法构建比较科学的「边」。在不同场景下可能适用不同的边。

0.2 间接距离

上面的5~9类属于间接联系，使用间接联系多少已经是在推断了（A-B并无“实边”）。综合起来看「频率权重的共同邻居」效果比较好（我比较喜欢简称这种间接为FWCN）

之后我会结合一些样例数据进行探索：

• 1 机器。使用我的局域网台式机
• 2 数据。50000+企业的60000+边的关系,存储在Neo4j中。
  

局域网台式机(14年的老机器了，很期待明年上AMD 5900/5950 12核/16核+128G 内存+ 3080显卡)：

通过局域网启动了Jupyter,因此在Mac上使用起来无违和感。（想要自己搭的化可以参考Python - 装机系列3 FRP、建模杂谈系列33-自有算网的迁移计算jupyter）

用大内存机器是因为要进行矩阵计算（等双11买到3060ti可以用张量计算进行速度对比），可以参考Python 图算法系列3-矩阵计算图指标。

丐版MAC实在不适合搞计算，以1万X1万的矩阵计算，至少1G的内存(numpy每个元素最小1字节)甚至8G的内存（float类型）。

1 图的模式查询

这部分很灵活，可以针对全体图数据库查询，也可以对子图进行查询。通常来说，子图才是最好的基础单元。

六度分离（六度区隔）理论（Six Degrees of Separation）：“你和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”根据这个理论，你和世界上的任何一个人之间只隔着五个人，不管对方在哪个国家，属哪类人种，是哪种肤色。

图的模式查询和业务比较相关，我这里随便先来两个
查询节点的度，出度和入度

match (n:enterprise)
with
size((n)--()) as degree,
size((n)-[:invest]->()) as out_degree,
size((n)<-[:invest]-()) as in_degree,
n
return n.eid, degree, out_degree, in_degree
limit 50


2 聚类算法

2.1 按是否一次性计算

世界很小，图很大

2.1.1 All-in-Memory

在这个例子中，因为图的节点数和边数不超过10万，所以可以全图读入。

• 1 使用cypher语句读取所有的边
• 2 使用py2neo读进内存
• 3 使用networkx进行重新构建

获取所有边的cypher：

match (n:enterprise)-[r:invest]->(n1:enterprise)
return n.eid, n1.eid


在python里执行：

# 获取数据测试
the_cypher = &＃39;&＃39;&＃39;match (n:enterprise)-[r:invest]->(n1:enterprise)
return n.eid as n1, n1.eid as n2 limit 3&＃39;&＃39;&＃39;
test_rels = graph.run(the_cypher).data()


我额外给单元格加了一个%%timeit魔法方法，给该步骤计算时间。
去读全部的关系（大概需要10秒时间）

【注意】服务器要在启动时给容器加上允许访问的数据库端口（否则端口不通，数据不来）

接下来就读入networkx包进行分析，networkx期望的格式如下:

2.1.2 Off-line

在实际应用中一定要考虑可以分批计算的离线算法：计算一批，存储一批，再计算一批。基本可以确定的是用动态规划的方法，具体怎么做我之后探索一下。

2.2 按聚类方法

先将数据读入

边少了一些，应该是存在自环和重复。看一下图的全貌（因为要画5万+节点和边，会比较慢）：

对应主机的资源占用（只是一个cpu在跑，内存很高，要放在MAC里面肯定跑挂了）：

哈哈，牛皮吹破了。我还是放弃了，不能打印这么大的图。以下是3600个点的图

2.2.0 按连通性分割图

# 图的连通性
def get_conngraph(C):res = [x for x in sorted(nx.connected_components(C), key=len, reverse=True)]return res
cong = get_conngraph(g)


首先根据图本身边的连接性，可以把图分为若干个连通子图（连通图还是比较多的）。

但可以看到，大部分的节点和关系都在g0（极大连通子图）

2.2.1 社区发现

根据已有的数据分为连通图相对是容易的，关键的一步是将连通的图再打散为若干个社区。从连通图再到社区的分割方法是不唯一的，这里只用常见（python调起来比较方便的方法）

# 将极大连通子图进行分割
the_subg = g_dict[&＃39;g0&＃39;]
partition = community.best_partition(the_subg)
node_cluster = pd.Series(partition)
mod = community.modularity(partition,the_subg)
print(&＃39;Modularity is 模块度是用来判断分割的有效性的&＃39; ,mod)
---
Modularity is 0.8940344871302761


社区节点数量的统计

# 选取一个社区（1），看它的连通性
g0c1 = g.subgraph(set(node_cluster[node_cluster==1].index))
g0c1g = get_conngraph(g0c1)
# 把最大的连通子图拿出来
g0c1g0 = g.subgraph(g0c1g[0])
# 3602，说明分出的社区没有断开的连接
print(nx.info(g0c1g0))
---
Name:
Type: Graph
Number of nodes: 3602
Number of edges: 5520
Average degree: 3.0650


如果图还是太大，那么可以迭代拆分，但拆分不会需要太多层级的（小世界）。

2.2.2 随机拆边

理论上可行，但是本次例子没有这样的需要。例如如果社区拆分不符合算法迭代指标（例如模块度）的要求，那么算法不可直接再拆分。但是从数据角度上，我们可以随机删掉10%或者20%的边，那么比较弱的关联就可能会被断开，从再次往下分。

3 分类算法

3.1 未见关系的推测

如果我们的数据中明确知道A认识B，那么我们可以通过查询获得这个事实结果。但有一种可能是A认识B，但是数据中并未显示，因此需要推断。
这里我们通过计算FWCN距离来进行一个简单的推断。这部分内容我在之前的文章有介绍过，现在正好有规模合适的图，可以再进行一次计算。

• 1 根据FWCN的算法通过for的方式计算结果
• 2 根据邻接矩阵的方式计算结果（计算主机上有32g内存，足够了）

当然我们要得到的结论是：A没有声称他认识B,但我们推断出了这样的结果。

先看看对当前子图的边

只要遍历节点，通过neighbors函数就可以获取这个节点的临边。FWCN需要计算朋友的朋友，所以这是一个n方的问题。我们说不定还可以利用cypher来加快这个查询，可以参考我的这篇文章。

我们一个一个来，先来看看计算FWCN的计算定义：

假设要计算A和B之间的FWCN， 先找出A和B的共同朋友。然后计算这个朋友度的倒数作为权重，为了不发生溢出，所以使用了对数倒数替代倒数。

简单的来说，看A和B的关系怎么样，就挨个看看他们的朋友，多个朋友多条路。如果他们的朋友C本身就是社交狂，C的存在对于衡量A和B的关系就不大。如果朋友D是个比较内敛的人，总共就只有A和B两个朋友，那么对于衡量A和B的关系就是一个比较重要的权重。
函数如下：（代码其实表达的更清晰）

def cal_FWCN(g, A, B):# A的邻居An = list(nx.neighbors(g, A))# B的邻居Bn = list(nx.neighbors(g, B))# A和B的共同邻居 CN of Two NodesABcn = list(set(An) & set(Bn))# 计算FWCNw = 0if len(ABcn):for cn in ABcn:tem_de = g.degree(cn)tem_w = np.log(tem_de)**-1w += tem_wreturn w

3.1.1 For循环计算

我们来看看需要计算的数量（看来产生了组合爆炸， 接近650万个可能边）

我们先计算10000条边，看看时间

问题似乎不大，估计很点之间就完全没有任何共同邻居，所以很快就过了。

总共花了23秒，作为实验这个计算规模刚刚好。结果得到了17万条具有FWCN数值的边。

意思是A和B节点的关系值是0.34。
我们先奔着应用目标去，这个计算发现了哪些“潜在”关系。

5520是原始数据，175836是推断的（当然可以过滤掉很多）， 791是两者交集，说明比较健壮？这个留待后续业务的验证吧。

下面我们还要做两个测试，计算FWCN。虽然在这个例子中20多秒就算好了，但是如果节点是1万个的话可能就呵呵了。而且如果图的总规模是1亿个节点的话… (20s X 150 X 10000 = 3千万秒)

• 1 矩阵计算
• 2 cypher查询

3.1.2 矩阵计算

矩阵计算本质上就是使用空间换时间，矩阵计算会使得单核满载。首先我们把图的关系表达为邻接矩阵，然后使用矩阵点乘替代for循环。特别注意：矩阵

对于1万个节点的子图， 其关系矩阵有1亿个元素，如果每个元素8字节，那么总共是800M大小。

我之前犯了一个错误，用稀疏矩阵去作为选择向量。例如本例组合大约有650万种，每个组合为一个3600个元素的变量。这样点乘需要的格子数大约是234亿个，那么一次性的计算大约是187.2G的内存。

矩阵适合密集的计算，每个元素都要有实际意义。

另外我发现numpy的数据类型最好就是float的。实测情况是，当元素为int型，计算矩阵点乘的时间非常长，使用htop看到只有一个cpu核在工作；而为float型时计算非常快，所有的核都参与了计算。

矩阵计算的部分我需要进行一些修改, 不能直接蛮干（存在组合数）

• 1 筛选
• 2 计算

for循环的方法中其实是蕴含这一步的，如果两个节点没有交集，那么就不去计算其邻居节点了。所以对于大量稀疏的关系，很快就跳过了。

另外，对于邻接矩阵的计算应该使用sparse方式（稀疏矩阵）。

–后补–

3.1.3 Cypher查询

如果我们使用cypher，第一步先用子图中的点进行匹配查询：

• 1 先筛选出具有共同朋友的关系
• 2 基于这些关系获取邻居节点的度
• 3 将数据返回来，再由python计算权值

本质上cypher也是在进行for循环计算，唯一可能有优势的是查询关系的速度，而对应的代价是传输数据的开销。

–后补–

3.2 未来建立关系的预测

本次例子中缺少时间变量，以后有机会再补。

其他

这样的写法导致了内存的极速增加，每太理解原因。可以看到对于选择矩阵，叠加到40万行时其数据对象大小不过3.4M，但是内存直接飙到了10G。我猜是列表对象里面装了太多的numpy对象导致的。

内存：

使用np.hstack来进行纵向叠加，可以参考这篇文章。

可以看到，虽然np对象大小增长的很快，但是内存并没有暴增。说明了之前的猜测是对的。numpy应该是具有一定开销的，整个连接过程非常慢。

解决方法：使用列表进行基本的向量元素拼接，变成一个矩阵后直接转换。

还有一个大坑…

没发现numpy的int类型点乘这么慢（感觉是计算机制是完全不同的），要转成浮点数算才快。以前没有注意过，大多数情况的确也是用浮点计算的。