(整理)SNAP简介与应用.

2021年2月28日发(作者：开罐器)

精品文档

SNAP

简介

SNAP(

S

tanford

N

etwork

A

nalysis

P

latform

)

是一个通用的、能高效的分析和处理 大型网

络的系统。

它支持图和网两种数据结构。

其中，图描述的是拓扑结构，

即每个结点都有一个

唯一 的整数

id

，

结点之间的边可以是有向 的，

也可以是无向的，

并且两个结点之间可以有多

条边；

网可以看成是一种结点和

（或者）

< p>
边上赋有数据的图。

这些数据的数据类型可以很容

易的作为模板参数传递

，

这就为实现那些在其结点和边上有着丰 富数据的各种各样的网络提

供了一种快速便捷的方法。下面是对

SNAP

支持的两种数据结构的进一步的描述。

SNAP

支持的图的类型：

?

无向图

(

TUNGraph

)

：在一对结点之间 只有一条无向边。

?

有向图

(

TNGraph

)

：在一对结点之间只有一条有向边。

?

有向多重图

(

TNEGraph

)

：在一对结点 之间有任意多条有向边。

SNAP

支持的网的类型：

?

有向结点网

(

TNodeNet

)

：每个结点上都有权值的有向图。

?

有向结点

/

边网

(

TNodeEDatNet< TNodeData, TEdgeData>

)

：每个结点和 每条边上都

有权值的有向图。

?

有向结点多重网

< br>(

TNodeEdgeNet< /p>

)

：每个结点和每条边上

都有权值的有向 多重图。

?

巨型网

(

TBigNet

< p>
)

：

有着数以亿计条边的有向结点网，

< p>
这种网必须用高

效的内存来实现并且要避免有内存碎片。其中，边的数量要 取决于计算机的

RAM

有多大。

SNAP

库的核心是用

C++

语言编写的，

并且进行了优化以实现最优性能 和最紧凑的图表

示。它可以很容易的对一个有着数以亿计的结点和边的大型网络进行缩放

(

scales

to

)

，可以

高效的处理大图，

可 以计算结构属性，

还可以生成正则图和随机图，

而且它还支持结 点和边

上的一些属性。另外，大图的可伸缩性是

SNAP

的另一个优点，即在计算的时候可以动态

的改变图或表的结点、边和属 性。

SNAP

最初是由

Jure

Leskovec

在他的博士研究过程中开发的，它的第一版在

2009

年

12

月发布 。

SNAP

运用了一个像在

Jozef

Stefan

Institute

开 发的

GLib

通用的标准模板库

。

SNAP

和

Glib

都在积极开发中并且应用到了大量的学术研究项目和工程项目中。

这是一个怎样创建和应用有向图的例子：

// create a graph

PNGraph Graph = TNGraph::New();

Graph->AddNode(1);

Graph->AddNode(5);

Graph->AddNode(32);

Graph->AddEdge(1,5);

Graph->AddEdge(5,1);

Graph->AddEdge(5,32);

< p>
每个结点有明确的

id,

但是这个

id

可以是任意的，不是必须从

0

开始连续编号。在一个

多重图

(

T NEGraph

)

中，每条边有明确的整数

id

。在有向图和无向图中，边没有

id

< br>，它们

用一个结点对来标示。

SNAP

使用智能指针，所以没有必要显式的删除图对象。当图对象不再被使用时，它们

精品文档

精品文档

就会进行自毁。在类名中，

前缀

P

代表指针，前缀

T

代表类型

。

创建网的方法和创建图的方法是一致的。

关于迭代器

SNAP

的很多操作是基于结点和边的迭代器进行的。

这些迭代器允许高效实现网络上的

那些算法而不必考虑网络的类型（有向、无向、图或是网）

，同 时它们也允许针对特定类型

网络的具体实现。

下面是迭代器的一个例子：

// create a directed random graph on 100 nodes and 1k edges

PNGraph Graph = TSnap::GenRndGnm(100, 1000);

// traverse the nodes

for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++)

{

printf(

id

%d

with

out-degree

%d

and

in-degree

%dn

Deg(),

eg());

}

// traverse the edges

for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++)

{

printf(

}

// we can traverse the edges also like this

for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++)

{

for (int e = 0; e < Deg(); e++)

{

printf(

}

}

所有的图和网的数据类型中都定义了结点和边的迭代器。

通常情况下，

图和网的数据类型运

用下列函数来返回各种各样的迭代器：

BegNI(): iterator to first node

EndNI(): iterator to one past last node

GetNI(u): iterator to node with id u

BegEI(): iterator to first edge

EndEI(): iterator to one past last edge

GetEI(u,v): iterator to edge (u,v)

GetEI(e): iterator to edge with id e (only for multigraphs)

结点迭代器通常会提供如下功能：

GetId(): return node id

精品文档

精品文档

GetOutDeg(): return out-degree of a node

GetInDeg(): return in-degree of a node

GetOutNId(e): return node id of the endpoint of e-th out-edge

GetInNId(e): return node id of the endpoint of e-th in-edge

IsOutNId(int NId): do we point to node id n

IsInNId(n): does node id n point to us

IsNbhNId(n): is node n our neighbor

另外，网的迭代器还允许方便的访问数据：

GetDat(): return data type TNodeData associated with the node

GetOutNDat(e): return data associated with node at endpoint of e-th out-edge

GetInNDat(e): return data associated with node at endpoint of e-th in-edge

GetOutEDat(e): return data associated with e-th out-edge

GetInEDat(e): return data associated with e-th in-edge

输入输出

我们可以用

SNAP

很容易的以多种格式保存和加载网络。虽然

S NAP

内部是以紧凑的二进

制格式保存网络，但是它可以以文本 和

XML

格式来保存和加载网络。

例如：

// generate a network using Forest Fire model

PNGraph G = TSnap::GenForestFire(1000, 0.35, 0.35);

// save and load binary

{ TFOut FOut(

{ TFIn FIn(

// save and load from a text file

TSnap::SaveEdgeList(G2,

PNGraph G3 = TSnap::LoadEdgeList(

处理图和网

SNAP

提供了丰富的功能来高效的处理图和网。这些功能的函数实现是命名空间

TSn ap

的

一部分。所有的函数都支持任意类型的图或网。

例如：

// generate a network using Forest Fire model

PNGraph G = TSnap::GenForestFire(1000, 0.35, 0.35);

// convert to undirected graph TUNGraph

PUNGraph UG = TSnap::ConvertGraph(G);

// get largest weakly connected component of G

PNGraph WccG = TSnap::GetMxWcc(G);

// get a subgraph induced on nodes {0,1,2,3,4,5}

PNGraph SubG = TSnap::GetSubGraph(G, TIntV::GetV(0,1,2,3,4));

// get 3-core of G

PNGraph Core3 = TSnap::GetKCore(G, 3);

精品文档

精品文档

// delete nodes of degree 10

TSnap::DelDegKNodes(G, 10);

计算结构属性

SNAP

提供了丰富的功能来高效的计算网络的结构属性。这些功能的函数实现是命名空间

TSnap

的一部分。所有的函数都支持任意类型的图或网。

例如：

// generate a Preferential Attachment graph on 1000 nodes and node out degree of 3

PUNGraph G = TSnap::GenPrefAttach(1000, 3);

// get distribution of connected components (component size, count)

TVec > CntV; // vector of pairs of integers (size, count)

TSnap::GetWccSzCnt(G, CntV);

// get degree distribution pairs (degree, count)

TSnap::GetOutDegCnt(G, CntV);

// get first eigenvector of graph adjacency matrix

TFltV EigV; // vector of floats

TSnap::GetEigVec(G, EigV);

// get diameter of G

TSnap::GetBfsFullDiam(G);

// count the number of triads in G, get the clustering coefficient of G

TSnap::GetTriads(G);

TSnap::GetClustCf(G);

应用

< /p>

图的时序演进

--

致密化法则和直径缩小

随着时间的推移，图是怎样演进的？针对这个问题，常见的认 识是：随着时间的推移，

图的平均度数保持恒定，

它的直径缓慢 增大。

我们的发现是：

随着时间的变化，网络以指数

< p>
的速度变的更密集（

Densification Power Law

）

，直径变得越来越小。

图的模式（

pattern

）

?

幂次规律

?

小世界理论（六度空间理论）

?

社区结构

图的模型

(model)

：

< p>
（给定结点数

N

和边书

E

，如何生成一个反映真实世界的图？）

?

随机图

随机选取两个点，然后连接起来，如此继续下去。

这样做不符合 幂次定律，

而且也

没有社区结构。

?

偏好连接

添加一个结点，然后创建

M

条出该结点 的连接。进入该结点的连接的数量正比于

它的入度。

这会形成密 集的地方越密集的现象

（

rich get richer p henomena

）

。

这能够

很好的解释幂度律分布，但是所有的结点都有相同的出度。

?

拷贝模型

精品文档

精品文档

添加一个结点，

< p>
选择添加边的数量，

选择一个随机结点然后将它的连接拷贝过去

< p>
（成

为邻居）

。这样生成的图，符合幂度律分布< /p>

深入了解图的信息处理：

?

异常检测：异常行为，图的演进。

?

预测：根据过去预测未来

?

仿真新算法

?

图像采样：

许多真实世界的图太大不能进行处理，

只能通过采样得到采样图，

对采

样图进行处理。

图的时序演进：

< br>T

时刻，

结点数为

N(t)

，

边数为

E(t)

。

T+1

时刻，

结点数为

2*N(t)

，

边数为

，< /p>

其中

a

是致密化的指数，且

1

≤

a

≤

< br>2

：

a=1

< br>：线性增长

-

出度是个常数。

a=2

：二次增长。

已经存在的图的生成模型没有指数致密化和直径变小的特点。

本文中我们找到两 个比较

好的模型：

社区结构连接（

community guided atta chment

）

:

服从致密化。

森林火灾模型：服从致密化，直径变小和幂律度分布。

运用克罗内克乘法来生成具有真实感的图和进行图的演进

静态图模式（

static graph pattern

）

：

?

幂律度分布

?

小世界

?

有效半径：

90%

的结点对在此距离上是可达的。

?

陡坡图：

图的邻接矩阵的特征值服从幂次律。

网的值（主特征向量的分量）也服从幂次律。

时序图模式（

temporal graph pattern

）

：

传统观点

—

恒定的平均度数：边的数量随着结点的数量 线性增长。

—

缓慢增 大的直径：随着网络规模的变大，两结点之间的距离也逐渐增大。

近来的发现

—

幂次律致密化：随着时间的推移，网络变得越 来越密。

—

直径减小：随着网络规模的增大，直径逐渐减小。

以上的所有这些模式在许多生活中真实的图中都可以观察到：

?

World wide web [Barabasi]

?

On- line communities [Holme, Edling, Liljeros]

?

Who call whom telephone networks [Cortes]

?

Autonomous systems [Faloutsos, Faloutsos, Faloutsos]

?

Internet backbone

–

routers [Faloutsos, Faloutsos, Faloutsos]

?

Movie

–

actors [Barabasi]

?

Science citations [Leskovec, Kleinberg, Faloutsos]

精品文档

精品文档

?

Co-authorship [Leskovec, Kleinberg, Faloutsos]

?

Sexual relationships [Liljeros]

?

Click-streams [Chakrabarti]

现在的问题是给定结点数和边数，怎么生成具有以上所有 模式的图，怎么证明这些模式？

关于图生成器，以前已经有很多研究：

?

Random graph [Erdos and Renyi, 60s]

?

Preferential Attachment [Albert and Barabasi, 1999]

?

Copying model [Kleinberg, Kumar, Raghavan, Rajagopalan and Tomkins, 1999]

?

Community Guided Attachment and Forest Fire Model [Leskovec, Kleinberg and Faloutsos, 2005]

?

Also work on Web graph and virus propagation [Ganesh et al, Satorras and Vespignani]++

但是，所有这些生成的图都 不能同时满足所有的模式，而且我们也不能得到相应的证明。

经过研究，我们提出了通过克罗内克积来生成图：

中间阶段

两图的克罗内克积的定义：

?

矩阵

A< /p>

和矩阵

B

的克罗内克积如下：

< p>

N*M

K*L

N*K

X M*L

?

我们定义两图的克罗内克积为两图的邻接矩阵的克罗内克积。

我们提出了一个通过迭代使用克罗内克积来生成图的增长序列：

精品文档