Data Mining 笔记-1 社交网络图挖掘

图的邻居性质

有向图和邻居

1. 有向图（directed graph）：是指一个包含节点集合和有向边集合的图，每条有向边写成$u → v$，其中u为有向边的源节点（source），$v$为目标节点（target）。所有的无向图都可以用有向图来表示，无向边$(u,v)$可表示为$u → v$和$v → u$。
2. 路径（path）：值一个节点的序列$v0, v1, …, vk$，其中对于每个$i=1, 2, …, k-1$，都存在有向边$vi → v_{i+1}$。该路径的长度（length）为$k$，即该路径上的有向边数目。长度为k的路径上有$k+1$个节点，因此节点到自己的路径的长度为0。
3. 节点$v$的$d$径内邻居（neighborhood of radius）：是指$v$在$d$步路径之内能达到的节点$u$的集合，记为$N(v,d)$。如果$V$是一个节点集合，那么$N(V,d)$是指$V$中节点在$d$步路径之内能达到的节点集合。
4. 节点v的邻居描述（neighborhood profile）：是其邻居$N(v,1), N(v,2), …$的大小构成的序列$∣N(v,1)∣, ∣N(v,2)∣, …$。这里不包含$N(v,0)$，因为其大小永远为1。邻居描述可以反映哪个节点（在每个相等路径长度上，该节点的邻居大小总是大于或等于其他节点）更接近网络中心。

图的直径

1. 强连通图（strongly connected）：任一节点到其他节点之间都存在路径。

2. 直径（diameter）：满足下列条件的最小整数$d$：对于图中任何两个节点$u$和$v$，都存在一条从$u$到$v$的长度小于或等于$d$的路径。（仅对无向图、 强连通图有意义）

   可以通过不断增加径长计算图的邻居大小来得到图的直径，直到邻居中不能再增加节点为止。即对于每个节点$v$，找到那个使得$∣N(v,d)∣ = ∣N(v,d+1)∣$成立的最小$d$。这个$d$是从$v$到其他任意可达节点的最短路径长度的紧致上界（tight upper bound），称为$d(v)$。

   如果图是强连通的，则图的直径为$maxv(d(v))$。

传递闭包和可达性

1. 传递闭包（transitive closure）：是指节点对$(u,v)$的集合，其中从$u$到$v$存在一条长度大于等于0的路径，可写成$path(u,v)$。
2. 节点间的可达性（reachability）：如果$path(u,v)$为真，则称$u$可到达（reach）$v$。
3. 计算传递闭包的问题：就是寻找$path(u,v)$为真的所有节点对$(u,v)$。
4. 可达性问题：给定图中节点$u$，寻找所有满足条件$path(u,v)$为真的$v$。

参考链接：link