复杂网络中的模体motif（python模体检测和随机网络生成）

关于复杂网络中模体研究的python实践

模体定义

“在复杂网络中发现的某种相互连接的模式个数显著高于随机网络”。所谓互相连接的模式，在三个节点组成的有向图，一共有如下 13 种可能，其中每一种，如果在网络中出现的概率比随机网络中明显高一截，就可以看成是一个模体。模体相关的研究，又被称为基元，具体可参考《复杂网络基元研究方法及应用》这本书。
参考知乎文章，链接: https://zhuanlan.zhihu.com/p/138822532

*请注意图中的序列不能重复计算。比如9包含2，但是在计算网络中模体2时，9不能算作是三个2组成的。

模体的检测方式

import networkx as nx
import igraph
import pandas as pd
import numpy as np
import itertools
import matplotlib.pyplot as plt
#import public_motif as motif

M8 = [[0, 1], [1,2]]
Net = [[1,4],[0,2],[2,1],[1,0]] 
graph_igraph = igraph.Graph(Net, directed=True)
motif_igraph = igraph.Graph(M8, directed=True)
#下面的函数是判断graph_igraph中是否含有和motif_igraph同构的子图，并且返回该子图的点序列。induced=True代表严格按照网络模体概念计算，2和9不同。Flase代表9也含有2，会被返回。
mappings = graph_igraph.get_subisomorphisms_lad(motif_igraph, induced=True) 
mappings_set = set(tuple(sorted(i)) for i in mappings)
for i in mappings_set:
	print(i)
结果：
(1, 2, 4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

具体请参考：链接: https://www.pythonf.cn/read/176566

随机网络的生成方式

因为网络模体一般需要对照与其具有相同度分布的随机网络进行对比，这里介绍一种相同度序列的随机网络的生成方式。

sequence = [ , ...]
random_degree_sequence_graph(sequence) 
#返回的是一般的networkx中的对象 Graph，可以通过属性nodes和edges遍历其中的点和边。
for k in G.edges():
	print(k)
for k in G.nodes():
	print(k)
结果：
(0, 2)
(0, 3)
(0, 1)
0
1
2
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

要注意，这样生成的网络是无向网络。对有向网络该如何生成呢？networkx也提供了函数

D = nx.DiGraph([(0, 1), (1, 2), (2, 3)])
din = list(d for n, d in D.in_degree())
dout = list(d for n, d in D.out_degree())
din.append(1)
dout[0] = 2
# We now expect an edge from node 0 to a new node, node 3.
D = nx.directed_configuration_model(din, dout)
1
2
3
4
5
6
7

详情请参考networkx官方文档。链接: networkx度序列随机图
更新：上述的生成有向图的方法存在问题，他生成的有向图存在平行边，和自环。不符合比较随机图的条件。查找资料后，可以参考这里提到的两种方法。链接: networkx度序列随机图。
其中交换边的方法：这是一个需要迭代的方法。具体步骤是：

1：从源图里随机找到2组边，比如A-B，C-D；
2：然后交换这两条边，形成A-D，C-D，如果碰到交换边后会自己指向自己，或者形成了重复，就不交换；
3：迭代进行Q ∗ ∣ E ∣ Q*|E|Q∗∣E∣次，这里的Q QQ够大后，比如100，网络基本能变成随机的。
————————————————
程序只需要将原图中的边[i,j]存进列表，随机选取列表中的两条边，交换 j1,j2 就行。原文链接：https://blog.csdn.net/infovisthinker/article/details/104563033

后续

后面就是将原图和随机图的模体进行对比了，参考论文：Superfamilies of Evolved and Designed Networks