数据分析之图算法: 基于Spark和Neo4j

图论及其概念

｜

19

图的

最大密度

是指其完全图中可能存在的关系数。可以通过公式

2

)1(N

Max

−

=

N

D

来计算，

其中

N

为节点数。使用公式

)1(

)(2

D

−

=

NN

R

来度量

实际密度

，其中

R

是关系数。图

2-10

展示

了

3

个度量无向图实际密度的例子。

稀疏图

密度 = 0.3

稠密图

密度 = 0.8

完全图（团）

密度 = 1.0

D =

−

25

66 1

()

()

D =

−

212

66 1

()

()

D =

−

215

66 1

()

()

图 2-10：检查图的密度有助于评估意外的结果

虽然没有严格的分界线，但是任何实际密度接近最大密度的图都可以看作稠密图。大多数

基于真实网络的图较为稀疏，且节点总数和关系总数之间近似于线性相关，在物理因素发

挥作用的情况下更是如此，例如一个节点能够连接多少电线、管道、道路或友谊等都是有

实际限制的。

针对极其稀疏或稠密的图执行某些算法会返回无意义的结果。一方面，如果图太稀疏，那

么可能没有足够的关系来支撑算法计算出有用的结果。另一方面，在连接非常稠密的节点

之间不会有太多额外信息，这是因为它们的关系已经足够紧密了。高密度会扭曲一些结果

或者增加计算复杂度。在这些情况下，过滤相关子图是一种实用方法。

2.3.6

　单部图

、

二部图和

k

部图

大多数网络包含具有多种节点和关系的数据，然而图算法通常只考虑一种节点和一种关

系。只有一种节点和一种关系的图有时称为

单部图

。

二部图

的节点可以划分成两个集合，其关系仅连接一个集合的节点和另一个集合的节点，

如图

2-11

所示。该图有两个节点集合：一个观众集合和一个电视剧集合，而且只存在两个 ...