Triangle Count算法

本文主要是介绍Triangle Count算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.传统算法

1.1算法描述

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}两个三角形。

1.2算法实现

def triangleCount(graph):count = 0tringle = []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 += 1tringle.append((srcId, destId, vertexId))print("===================================")print("Triangle Count: ", count)print(tringle)if __name__ == "__main__":#directed graphgraph = {0: [1, 2], 1: [2, 3], 2: [3], 3: []}#undirected graphgraph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}triangleCount(graph)

2.基于矩阵的实现

2.1算法描述

其实，我们换个角度思考，会发现Triangle Count的算法有一个更简单的方法：如果结点i既能通过一条路径到达结点j，又能通过两条路径到达结点j（假设经过的中间结点是k），那么结点i、j、k就可以构成一个三角形。
如此一来，不由的就想起了邻接矩阵A，其 的含义。 中的元素 表示从结点i经过k路径到达结点j的通路总数。如果不太清楚，可以参考 基于矩阵实现的Connected Components算法 中的介绍。

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

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

其邻接矩阵A和 分别是：

则可得，

2.2算法实现

Python代码实现如下：

from numpy.random import rand
import numpy as npdef init(dimension):mat = np.zeros((dimension, dimension))mat[(rand(dimension) * dimension).astype(int), (rand(dimension) * dimension).astype(int)] = 1return matdef triangleCount(adjacencyMat):biAdjacencyMat = np.dot(adjacencyMat, adjacencyMat)countIntersect = np.logical_and(adjacencyMat, biAdjacencyMat)return countIntersectif __name__ == "__main__":adjacencyMat = np.array([[0, 1, 1, 0],[0, 0, 1, 1],[0, 0, 0, 1],[0, 0, 0, 0]])dimension = 4adjacencyMat1 = init(dimension)print(triangleCount(adjacencyMat))

这篇关于Triangle Count算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---