SNAP简介与应用

SNAP简介

SNAP(Stanford Network Analysis Platform)是一个通用的、能高效的分析和处理大型网络的系统。它支持图和网两种数据结构。其中，图描述的是拓扑结构，即每个结点都有一个唯一的整数id，结点之间的边可以是有向的，也可以是无向的，并且两个结点之间可以有多条边；网可以看成是一种结点和（或者）边上赋有数据的图。这些数据的数据类型可以很容易的作为模板参数传递，这就为实现那些在其结点和边上有着丰富数据的各种各样的网络提供了一种快速便捷的方法。下面是对SNAP支持的两种数据结构的进一步的描述。

SNAP支持的图的类型：

? 无向图(TUNGraph)：在一对结点之间只有一条无向边。 ? 有向图(TNGraph)：在一对结点之间只有一条有向边。

? 有向多重图(TNEGraph)：在一对结点之间有任意多条有向边。 SNAP支持的网的类型：

? 有向结点网(TNodeNet)：每个结点上都有权值的有向图。

? 有向结点/边网(TNodeEDatNet)：每个结点和每条边上都

有权值的有向图。

? 有向结点多重网(TNodeEdgeNet)：每个结点和每条边上

都有权值的有向多重图。

? 巨型网(TBigNet)：有着数以亿计条边的有向结点网，这种网必须用高

效的内存来实现并且要避免有内存碎片。其中，边的数量要取决于计算机的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);

每个结点有明确的id,但是这个id可以是任意的，不是必须从0开始连续编号。在一个多重图(TNEGraph)中，每条边有明确的整数id。在有向图和无向图中，边没有id，它们用一个结点对来标示。

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 %d\\n\NI.GetOutDeg(), NI.GetInDeg()); }

// 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 < NI.GetOutDeg(); 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很容易的以多种格式保存和加载网络。虽然SNAP内部是以紧凑的二进制格式保存网络，但是它可以以文本和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提供了丰富的功能来高效的处理图和网。这些功能的函数实现是命名空间TSnap的一部分。所有的函数都支持任意类型的图或网。 例如：

// 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);

应用

图的时序演进--致密化法则和直径缩小

随着时间的推移，图是怎样演进的？针对这个问题，常见的认识是：随着时间的推移，图的平均度数保持恒定，它的直径缓慢增大。我们的发现是：随着时间的变化，网络以指数的速度变的更密集（Densification Power Law），直径变得越来越小。

图的模式（pattern） ? 幂次规律

? 小世界理论（六度空间理论） ? 社区结构 图的模型(model)：（给定结点数N和边书E，如何生成一个反映真实世界的图？） ? 随机图

随机选取两个点，然后连接起来，如此继续下去。这样做不符合幂次定律，而且也没有社区结构。 ? 偏好连接

添加一个结点，然后创建M条出该结点的连接。进入该结点的连接的数量正比于它的入度。这会形成密集的地方越密集的现象（rich get richer phenomena）。这能够很好的解释幂度律分布，但是所有的结点都有相同的出度。 ? 拷贝模型

添加一个结点，选择添加边的数量，选择一个随机结点然后将它的连接拷贝过去（成为邻居）。这样生成的图，符合幂度律分布

深入了解图的信息处理：

? 异常检测：异常行为，图的演进。 ? 预测：根据过去预测未来 ? 仿真新算法

? 图像采样：许多真实世界的图太大不能进行处理，只能通过采样得到采样图，对采

样图进行处理。

图的时序演进：

T时刻，结点数为N(t)，边数为E(t)。T+1时刻，结点数为2*N(t)，边数为，其中a是致密化的指数，且1≤a≤2：

a=1：线性增长-出度是个常数。 a=2：二次增长。

已经存在的图的生成模型没有指数致密化和直径变小的特点。本文中我们找到两个比较好的模型：

社区结构连接（community guided attachment）:服从致密化。 森林火灾模型：服从致密化，直径变小和幂律度分布。

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

静态图模式（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]