Triangle Count 算法

妖狐艹你老母 2022-06-17 22:13 161阅读 0赞

Triangle Count在社交网络分析中是非常有用的。这个三角形是一个三结点的小图，其中结点两两相连。假如，在Facebook上，你认识两个校友，而这两个校友彼此有相互认识，那么你们三个就组成了一个三角形。像这样的，社交网络拥有越多的三角形，其联系也就业紧密。  
Triangle Count的算法思想如下：

1.  计算每个结点的邻结点，
2.  对通过每条边的两个顶点相联的顶点的相邻点集合计算交集，并找出交集中id大于前两个结点id的结点，
3.  对每个结点统计Triangle总数，注意只统计符合计算方向的Triangle Count。

**注意：计算三角形时，要有计算方向（如，起始结点id<中间结点id<目的结点id）。**

假设结点A和结点B是邻居。结点A的邻结点集合是\{B，C，D，E\}，结点B的邻结点集合是\{A，C，E，F，G\}，而它们的交集是\{C，E\}。交集中的结点是结点A和结点B的共同邻结点，所以有\{A，B，C\}和\{A，B，E\}两个三角形。

def triangleCount(graph):  
count = 0  
tringle = \[\]  
for srcId in graph:  
srcSet = graph.get(srcId)  
for destId in srcSet:  
if (destId > srcId):  
destSet = graph.get(destId)  
for vertexId in destSet:  
if(vertexId in srcSet) and (vertexId > destId):  
count += 1  
tringle.append((srcId, destId, vertexId))  
print("===================================")  
print("Triangle Count: ", count)  
print(tringle)  
  
if \_\_name\_\_ == "\_\_main\_\_":  
\#directed graph  
graph = \{0: \[1, 2\], 1: \[2, 3\], 2: \[3\], 3: \[\]\}  
\#undirected graph  
graph = \{0: \[1, 2\], 1: \[0, 2, 3\], 2: \[0, 1, 3\], 3: \[1, 2\]\}  
triangleCount(graph)  
  
其实，我们换个角度思考，会发现Triangle Count的算法有一个更简单的方法：如果结点i既能通过一条路径到达结点j，又能通过两条路径到达结点j（假设经过的中间结点是k），那么结点i、j、k就可以构成一个三角形。  
如此一来，不由的就想起了邻接矩阵A，其 ![Center][]的含义。 ![Center][]中的元素 ![Center 1][]表示从结点i经过k路径到达结点j的通路总数。如果不太清楚，可以参考 *[基于矩阵实现的Connected Components算法][Connected Components]* 中的介绍。

现在不用我多说，大家也都猜到了出现在A和![Center 2][]相同位置中的非零值，就表示可以形成三角形，而非零值的个数即为Triangle Count。用公式表示为：

![Center 3][]

假如，有一个图拥有四个结点，如下：

![Center 4][]

其邻接矩阵A和 分别是：

![Center 5][]

则可得，

![Center 6][]

## 2.2算法实现 ##

Python代码实现如下：

**\[python\]** [ view plain][view plain] [ copy][view plain]

1.  from numpy.random import rand
2.  import numpy as np
3.  
4.  def init(dimension):
5.  mat = np.zeros((dimension, dimension))
6.  mat\[(rand(dimension) \* dimension).astype(int), (rand(dimension) \* dimension).astype(int)\] = 1
7.  return mat
8.  
9.  def triangleCount(adjacencyMat):
10. biAdjacencyMat = np.dot(adjacencyMat, adjacencyMat)
11. countIntersect = np.logical\_and(adjacencyMat, biAdjacencyMat)
12. return countIntersect
13. 
14. if \_\_name\_\_ == "\_\_main\_\_":
15. adjacencyMat = np.array(\[\[0, 1, 1, 0\],
16. \[0, 0, 1, 1\],
17. \[0, 0, 0, 1\],
18. \[0, 0, 0, 0\]\])
19. dimension = 4
20. adjacencyMat1 = init(dimension)
21. print(triangleCount(adjacencyMat))

[Center]: https://img-blog.csdn.net/20151208194455483?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220618/ce052ea4256144f9abf8c36ed3d5f89c.png
[Connected Components]: http://blog.csdn.net/u010376788/article/details/49805291
[Center 2]: /images/20220618/55fc992209ff4cfb87d57ae42016857f.png
[Center 3]: /images/20220618/bc3a17dd4dbd407ba484e8398de755b9.png
[Center 4]: /images/20220618/c9320fc557484f5486eb628655d8b9d9.png
[Center 5]: /images/20220618/73f860ca302249f0a77f9eaae21c961c.png
[Center 6]: /images/20220618/f1fdb0e3a01243c1b2a6144d9a74bb9b.png
[view plain]: http://blog.csdn.net/u010376788/article/details/50223157#