一种基于代数化的深度优先搜索的环路检测方法

1.本发明涉及社区网络有向图技术领域，具体涉及一种基于代数化的深度优先搜索的环路检测方法。


背景技术：

2.社交网络是参与社会活动的成员之间通过各种社会关系结成的网络结构，整个结构可以抽象为图论中的有向图表示。
3.社交网络形成的有向图中，个体可以抽象节点，表示组织、个人、网络id等不同含义的实体或虚拟个体；而个体间的关系可以抽象为带方向的边，是亲友、动作行为、收发消息等多种关系，将各个点联合起来。对社交网络的分析过程中，环路作为发现人际关系、操作关联关系和社交圈等特殊关系的重要结构需要被识别。
4.在图论研究中，环路是发现图性质和点之间关系的重要结构，在实践应用中环路可以在社交网络分析的场景中发挥作用。如此看来，如何在一个社交网络形成的有向图图中探测并找出所有的环路在获取图性质和点之间的关系中成为了研究的关键。
5.在有向图研究中，一个有向回路是一个非空的有向路径，其第一个与最后一个顶点相同。令有向图一个回路是一条非空路径(e1,e2,
…
,en),其顶点序列为(v1,v2,
…
,v
n,
v1)。一个有向环路，或者简单有向回路，是只有第一个与最后一个顶点相同的有向回路。
6.在有向图上的环可以被使用深度优先搜索(dfs)的方法，通过寻找一条连接当前顶点与之前顶点的边(它包含了一条后向边)，我们可以探测有向图上环的存在。所有dfs跳过的后向边都是某些环的一部分。在一个无向图上，指向父节点的边不能被算作后向边，但是找到已经被经过了的顶点意味着后向边的存在。许多拓扑排序算法也会探测环的存在，因为这些环会成为拓扑排序存在的障碍。另外，如果一个有向图被分成了几个强连通分量，那么环只会在这些分量内部存在，而不会连接这几个分量，因为环本身就是强连接的。对于有向图，还可以使用基于分布式信息的算法。这些算法的思路基于一条从一个顶点发出的信息可以通过环回到这个顶点。分布式环检测算法对于在计算机集群上使用分布式图处理系统来处理大规模的图很有帮助。
7.环路检测算法在业界有广泛的实现和研究，但图算法形式的基本数学算法已经停滞(如c++最著名的库boost中使用的是1970年的tiernan算法)，且随着数据规模的发展，在大规模图上进行环路检测成为一个难题。
8.因此在面临当前社会如此庞杂多元的社交网络结构形成的大规模图，如何进行高效的环路检测是尚未解决的问题。


技术实现要素：

9.有鉴于此，本发明提供了一种基于代数化的深度优先搜索的环路检测方法，能够有效地在社交网络中发现并输出所有规定长度内的环路，算法简单效率较高。
10.为达到上述目的，本发明的技术方案为：构建社交网络的有向图g(v,e)，其中v为社交网络结构中的点组成的集合，e为社交网络结构中边组成的集合；v的大小为n，e的大小为e；该方法将所述有向图g(v,e)作为目标图，执行如下步骤：
11.步骤一，将有向图中的点按照读取顺序从1至n编号。
12.步骤二，按照编号将所述有向图的点边信息以邻接矩阵a的形式存储到csr格式压缩矩阵中。
13.步骤三，在所述有向图的邻接矩阵中，选取起始点，用代数化的语言利用邻接矩阵和可达矩阵的思想进行环路检测，在环路检测过程中根据有向图和环路的数学性质进行路径扩展限定，扩展节点即下一个属于环路的节点；由此获得针对起始点的环路路径。
14.优选地，在环路检测过程中根据有向图和环路的数学性质进行路径扩展限定，具体包括三个限制条件，分别为
15.第一限制条件：扩展的下一个节点不能出现在当前路径内。
16.第二限制条件：对节点进行编号，扩展下一个节点的编号不能小于起始点的编号。
17.第三限制条件：扩展的下一个节点不能在上一个点的已经探索过的邻接点集内。
18.优选地，步骤三具体为：
19.设置起始点作为当前路径点，执行step301至step304获取环路路径，起始点个数至少为1个，起始点数量超过2个时，针对多个起始点同步执行步骤三至六，同步获取对应环路路径。
20.step301：对于当前路径点i，引用可达矩阵的思想，构建第i列为1，其余列为0的维数为1
×
n的行向量pi，将pi与矩阵a进行向量矩阵乘法，得到1
×
n的行向量p
1i
，判断p
1i
中第k列不为0表示由编号为i的点可以扩展路径到编号为k的节点。
21.step302：根据扩展到的节点的编号k按照三个限制条件进行逐一判断，全部满足之后加入当前路径path。
22.step303：判断当前路径path的长度是否达到预设的最大环路长度maxlen，若当前路径长度小于maxlen则，以k作为当前路径点返回step301，直接进行下一个节点扩展，若当前路径长度大于maxlen度则直接舍弃并回溯缩短路径，否则进入step304。
23.step304：判断当前路径path的首尾编号是否相同，若首尾编号相同时，当前路径即为一个基本环路，将环路路径添加到结果集中。
24.有益效果：
25.本发明提出了一个基于代数化的在表示社交网络的有向图中进行环路检测方法，能够有效地在社交网络中中发现并输出所有规定长度内的环路，该方法能够有效地在有向图中发现并输出所有规定长度内的环路，即保证了环路检测的正确性，又有在搜索过程中充分利用了代数化建模带来的并行化便利提升性能。本发明的技术方案有较高的计算效率，适用于大规模现实有向图数据集，性能上远远超过著名的c++boost库的环路检测接口。
附图说明
26.图1为本发明具体流程图。
具体实施方式
27.下面结合附图并举实施例，对本发明进行详细描述。
28.本发明提出了一种代数化的深度搜索方法并应用在环路检测中，设计了高效的计算方法，其流程如图1所示。
29.构建社交网络的有向图g(v,e)，其中v为社交网络结构中的点组成的集合，e为社交网络结构中边组成的集合；v的大小为n，e的大小为e；该方法将所述有向图g(v,e)作为目标图，一个有向环路，或者简单有向回路，是只有第一个与最后一个顶点相同的有向回路。
30.为了找出有向图g中所有的环路，本发明首先将节点编号重映射为以1为最小编号且编号顺序增大的点集合，然后读取边信息以csr压缩矩阵格式保存表示为邻接矩阵a(邻接矩阵，n个点，则矩阵为n
×
n为，第i行第j列的数字为1则表示i、j之间有边)，用代数化的语言利用邻接矩阵和可达矩阵的思想，减少循环层数并在矩阵本身保存一定信息来进行搜索，然后根据有向图和环路的数学性质进行路径扩展限定以达到剪枝减少无效路径搜索、避免重复搜错和重复的环路检测错误提升性能，具体来说有三个扩展节点限制：
31.第一限制条件：路径是一点一点地搜索出来的，扩展节点即下一个节点是否属于环路，扩展的下一个节点不能出现在当前路径内；该条件确保了路径是基本路径。
32.第二限制条件：对节点进行编号，扩展下一个节点的编号不能小于起始点的编号；该条件确保了每个回路只会被计算一次。
33.第三限制条件：扩展的下一个节点不能在上一个点的已经探索过的邻接点集内。该条件确保了每个基本路径只会被计算一次。点的编号实际体现为矩阵的行数或列数。
34.本发明的具体操作流程如下三个步骤：
35.步骤一，将有向图中的点按照读取顺序从1至n编号；
36.步骤二，首先读取有向图g的信息获取矩阵a。由于本方法只涉及0和1则对矩阵元素的具体值无需记录，而只需要记录不为0的位置。具体分为两个数组，col数组的第i个元素记录了第i个不为0的元素(此处为1)的列数，row数组第j个元素记录了前j-1行包含的非零元素的数量。对一个输入(i,j)表示有一条从编号为i的点到编号为j的点边，
37.步骤三，在所述有向图的邻接矩阵中，选取起始点，用代数化的语言利用邻接矩阵和可达矩阵的思想进行环路检测，在环路检测过程中根据有向图和环路的数学性质进行路径扩展限定，扩展节点即下一个属于环路的节点；由此获得针对起始点的环路路径。
38.步骤三具体为：
39.设置起始点作为当前路径点，执行step301至step304获取环路路径，起始点个数至少为1个，起始点数量超过2个时，针对多个起始点同步执行步骤三至六，同步获取对应环路路径；
40.step301：对于当前路径点i，引用可达矩阵的思想，构建第i列为1，其余列为0的维数为1
×
n的行向量pi，将pi与矩阵a进行向量矩阵乘法，得到1
×
n的行向量p
1i
，判断p
1i
中第k列不为0表示由编号为i的点可以扩展路径到编号为k的节点；
41.step302：根据扩展到的节点的编号k按照三个限制条件进行逐一判断，全部满足之后加入当前路径path；
42.step303：判断当前路径path的长度是否达到预设的最大环路长度maxlen，若当前路径长度小于maxlen则，以k作为当前路径点返回step301，直接进行下一个节点扩展，若当
前路径长度大于maxlen度则直接舍弃并回溯缩短路径，否则进入step304；
43.step304：判断当前路径path的首尾编号是否相同，若首尾编号相同时，当前路径即为一个基本环路，将环路路径添加到结果集中。
44.该过程使用矩阵向量乘法来表达，分别以所有点为起点进行搜索，引用可达矩阵的思想，以第i列为1，其余列为0为维数为1
×
n的行向量p与矩阵a做并行的向量矩阵乘法，向量p即代表了本次搜索的出发点，与矩阵a做的乘法等价于获取该点的所有邻居，得到1
×
n的结果向量p1，其中第k列不为0则表示由编号为i的点可以扩展路径到编号为k的节点。然后提取出向量p1中不为0的列数，假设向量p1第k列为1，如果节点k满足上述的三个数学条件则生成一个新的第k列为1，其余列为0为维数为1
×
n的行向量p2矩阵a做并行的向量矩阵乘法，进而生成p3直到达到规定的最大环路长度maxlen即生成到p
maxlen
之后停止该路径的本次搜索并回溯，以这样的递归乘法过程来模拟搜索。
45.在对三个扩展结点的限制条件进行判断时同样需要对矩阵和向量进行信息提取。对于第一个限制条件，在对中间结果向量p1不为0的列数提取得到列数集合后，先判断该列数对应编号的拓展节点是否已经在路径出现，如果已经出现则直接舍弃遍历下一个，否则生成新的向量继续递归进行矩阵向量乘法；对于第二个限制条件，将在递归过程中维护路径的起始节点编号，在对中间结果向量p1不为0的列数提取得到列数集合后，先比较该列数对应编号与起始节点编号的大小，如果小于起始点编号，否则生成新的向量继续递归进行矩阵向量乘法；对于第三个限制条件，因为对中间结果向量p1不为0的列数提取得到列数集合自然地形成一定顺序，向量生成的过程也是一个按照一定顺序遍历的过程，所以在做好并行化的同步设置后自然地满足条件。当扩展节点与起始节点相同时，判断当前路径长度是否大于规定的最小环路长度，若满足所有条件则加入结果集。
46.在社交网络中要对个体能力、群体结构、实体关系和综合情报决策等进行分析。将社交网络抽象为有向图结构之后，本发明能够输出社交网络有向图中的环路，该环路揭示了社交网络中关系紧密的群里，例如如互相关注的用户圈和相关联的推文信息，进一步通过对该环路上节点进行分析，可以发现群体之间的合作关系和相互差异。针对社交网络有向图中环路的提取和分析，能够分析社交网络的发展，比如信息圈的出现与消亡，网络之中哪些节点群之间有相似之处并可能发展为新的环路，由此制定政策、产业布局、人际交往等规划计划。
47.实施例：
48.本发明针对社交网络有向图进行环路检测，示例有向图如图1所示。下面对本发明作做具体实施方式的说明：
49.读取有向图信息生成矩阵a：
[0050][0051]
这里为了示例清晰图中为原矩阵a而不使用csr压缩矩阵，实际使用中使用压缩矩
阵节约存储空间：
[0052]
搜索推动过程具体为：
[0053]
1：初始化起始点，选取所有的点作为起点，本发明实施例设置以编号为1的顶点为起点的向量p0；
[0054]
p0＝(1 0 0 0 0 0)
[0055]
2：令p0与a相乘推动搜索，得到新的中间结果p1，p1的第i行中不为0的列就表示由编号为i的节点可以扩展到编号为节点，如此完成了第一轮扩展，得到结果为
[0056]
path＝{1}
[0057]
p1＝p0×
a＝(0 1 0 0 1 0)
[0058]
path1＝{{1-2},{1-5}}
[0059]
path1所示，向量p1第2列为1则path1中有路径{1
→
2}，第5列为1则path1中有路径{1
→
5}，如此同理其他所有顶点对应的向量中间结果可以堆叠成一个完整的中间结果矩阵，第i行代表着编号为i的点可以扩展到的邻接点；
[0060]
3：由于由顶点1可以扩展到2和5两个点，拆分为两个向量p
11
和p
12
分别与a相乘推动搜索得到新的中间结果p
21
和p
22
：
[0061]
p
11
＝(0 1 0 0 0 0)
[0062]
p
12
＝(0 0 0 0 1 0)
[0063]
p
21
＝p
11
×
a＝(0 0 1 0 0 0)
[0064]
p
22
＝p
12
×
a＝(0 1 0 0 0 0)
[0065]
path2＝{{1-2-3},{1-5-2}}
[0066]
4：如此完成了第二轮扩展，得到结果path2，如此同理其他所有顶点对应的向量中间结果可以堆叠成一个完整的中间结果矩阵，第i行代表着编号为i的点可以扩展到的邻接点；
[0067]
5：继续递归执行，直到完成所有的路径搜索得到最终结果。
[0068]
综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种基于代数化的深度优先搜索的环路检测方法，其特征在于，构建社交网络的有向图g(v,e)，其中v为社交网络结构中的点组成的集合，e为社交网络结构中边组成的集合；v的大小为n，e的大小为e；该方法将所述有向图g(v,e)作为目标图，执行如下步骤：步骤一，将有向图中的点按照读取顺序从1至n编号；步骤二，按照编号将所述有向图的点边信息以邻接矩阵a的形式存储到csr格式压缩矩阵中；步骤三，在所述有向图的邻接矩阵中，选取起始点，用代数化的语言利用邻接矩阵和可达矩阵的思想进行环路检测，在环路检测过程中根据有向图和环路的数学性质进行路径扩展限定，扩展节点即下一个属于环路的节点；由此获得针对起始点的环路路径。2.如权利要求1所述的一种基于代数化的深度优先搜索的环路检测方法，其特征在于，所述在环路检测过程中根据有向图和环路的数学性质进行路径扩展限定，具体包括三个限制条件，分别为第一限制条件：扩展的下一个节点不能出现在当前路径内；第二限制条件：对节点进行编号，扩展下一个节点的编号不能小于起始点的编号；第三限制条件：扩展的下一个节点不能在上一个点的已经探索过的邻接点集内。3.如权利要求2所述的一种基于代数化的深度优先搜索的环路检测方法，其特征在于，所述步骤三具体为：设置起始点作为当前路径点，执行step301至step304获取环路路径，起始点个数至少为1个，起始点数量超过2个时，针对多个起始点同步执行步骤三至六，同步获取对应环路路径；step301：对于当前路径点i，引用可达矩阵的思想，构建第i列为1，其余列为0的维数为1
×
n的行向量p
i
，将p
i
与矩阵a进行向量矩阵乘法，得到1
×
n的行向量p
1i
，判断p
1i
中第k列不为0表示由编号为i的点可以扩展路径到编号为k的节点；step302：根据扩展到的节点的编号k按照三个限制条件进行逐一判断，全部满足之后加入当前路径path；step303：判断当前路径path的长度是否达到预设的最大环路长度maxlen，若当前路径长度小于maxlen则，以k作为当前路径点返回step301，直接进行下一个节点扩展，若当前路径长度大于maxlen度则直接舍弃并回溯缩短路径，否则进入step304；step304：判断当前路径path的首尾编号是否相同，若首尾编号相同时，当前路径即为一个基本环路，将环路路径添加到结果集中。

技术总结
本发明公开了一种基于代数化的深度优先搜索的环路检测方法，涉及社区网络有向图技术领域，能够有效地在社交网络中发现并输出所有规定长度内的环路，算法简单效率较高。为达到上述目的，本发明的技术方案为：构建社交网络的有向图；该方法将社交网络的有向图作为目标图，执行如下步骤：将有向图中的点按照读取顺序从1至n编号。按照编号将所述有向图的点边信息以邻接矩阵A的形式存储到CSR格式压缩矩阵中。在所述有向图的邻接矩阵中，选取起始点，用代数化的语言利用邻接矩阵和可达矩阵的思想进行环路检测，在环路检测过程中根据有向图和环路的数学性质进行路径扩展限定，扩展节点即下一个属于环路的节点；由此获得针对起始点的环路路径。环路路径。环路路径。


技术研发人员：邱瑞亨 张志威 王国仁
受保护的技术使用者：北京理工大学
技术研发日：2023.03.10
技术公布日：2023/7/22