Triangle Count算法

我不是女神ヾ 2022-08-18 03:16 129阅读 0赞

# 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 = 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)

# 2.基于矩阵的实现 #

## 2.1算法描述 ##

其实，我们换个角度思考，会发现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代码实现如下：

from numpy.random import rand
    import numpy as np
    
    def init(dimension):
        mat = np.zeros((dimension, dimension))
        mat[(rand(dimension) * dimension).astype(int), (rand(dimension) * dimension).astype(int)] = 1
        return mat
    
    def triangleCount(adjacencyMat):
        biAdjacencyMat = np.dot(adjacencyMat, adjacencyMat)
        countIntersect = np.logical_and(adjacencyMat, biAdjacencyMat)
        return countIntersect
        
    if __name__ == "__main__":
        adjacencyMat = np.array([[0, 1, 1, 0],
                                 [0, 0, 1, 1],
                                 [0, 0, 0, 1],
                                 [0, 0, 0, 0]])
        dimension = 4
        adjacencyMat1 = init(dimension)
        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/20220731/0b2b236bb1ea44ef9d6004d81e976d57.png
[Connected Components]: http://blog.csdn.net/u010376788/article/details/49805291
[Center 2]: /images/20220731/49bfb3bdfd8b4188a9f6cfb1510c3902.png
[Center 3]: /images/20220731/545f263ca4a94e018b708b52aa8f6c0a.png
[Center 4]: /images/20220731/3baf059d9ab140a9b189e53a765376ff.png
[Center 5]: /images/20220731/6b7fe4a93abb44529540e57f991c43d5.png
[Center 6]: /images/20220731/c2a0f3c6567a4700974f195afd612589.png