场景介绍

拓扑度量类算法主要关注结点之间的连接，例如，在交通领域中的交通站点流量预测、公交地铁站点流量监测、重点路段流量监测、重点道路拥堵识别都涉及此类算法。

算法原理

TriangleCount算法

TC（TriangleCount，三角形计数）算法在大规模图数据计算领域，是社交网络分析的基本算法，可以计算出图网络中每个结点与其余结点形成的三角形个数，支撑数千万及上亿结点、十亿边数的无向网络图的三角形计数。

编程实例

本示例以TriangleCount（三角形计数）算法来介绍编程示例。

run API

API

       
            run[VD: ClassTag, ED: ClassTag](graph: Graph[VD, ED]): Graph[Int, ED]

功能描述
 计算图网络中每个结点的三角形个数。

TriangleCount算法时序图如图1所示。

图1 TriangleCount算法时序图

输入输出
1. 包名：package org.apache.spark.graphx.lib.TriangleCount
2. 类名：TriangleCount
3. 方法名：run
4. 输入：graph: Graph[VD, ED]
5. 输出：result: Graph[Int, ED]

使用TriangleCount样例

val sparkconf = new SparkConf().setAppName("modularityCompute").setMaster(host)
val sc = new SparkContext(sparkconf)
val input = sc.parallelize(Array((1,2),(1,3),(1,5),(1,4),(2,3), (3,4), (2,6),(4,5), (6, 5), (2,7),(3,7),(10,2),(10,4),(3,8),(4,8),(3,11),(11,5),(4, 9),(9,5)))
val graph = Graph.fromEdgeTuples(input.map(f=>(f._1.toLong,f._2.toLong)), 0)
val res = TriangleCount.run(graph)

样例结果

第一列为结点ID，第二列为该结点对应三角形个数。
```
4,4
11,0
1,3
6,0
3,4
7,1
9,1
8,1
10,0
5,2
2,2
```

runPreCanonicalized API

API

       
            def runPreCanonicalized[VD: ClassTag, ED: ClassTag](graph: Graph[VD, ED]): Graph[Int, ED]

功能描述
 计算图网络中每个结点的三角形个数。
API描述
 不可处理自环和双向边，输入图无自环和双向边时可以调用此接口。
输入输出
1. 包名：package org.apache.spark.graphx.lib.TriangleCount
2. 类名：TriangleCount
3. 方法名：runPreCanonicalized
4. 输入：graph: Graph[VD, ED]
5. 输出：result: Graph[Int, ED]

使用TriangleCount样例

       
            val input = sc.parallelize(Array((1,2),(1,3),(1,5),(1,4),(2,3), (3,4), (2,6),(4,5), (6, 5), (2,7),(3,7),(10,2),(10,4),(3,8),(4,8),(3,11),(11,5),(4, 9),(9,5)))
val graph = Graph.fromEdgeTuples(input.map(f=>(f._1.toLong,f._2.toLong)), 0)
val res = TriangleCount.runPreCanonicalized(graph)

样例结果

第一列为结点ID，第二列为该结点对应三角形个数。
```
4,4
11,0
1,3
6,0
3,4
7,1
9,1
8,1
10,0
5,2
2,2
```