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]

? 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和矩阵B的克罗内克积如下：

N*M K*L

N*K X M*L

? 我们定义两图的克罗内克积为两图的邻接矩阵的克罗内克积。 我们提出了一个通过迭代使用克罗内克积来生成图的增长序列：

克罗内克图符合所有的模式，但是它会产生阶梯效应：

所以我们提出一种随机克罗内克图： ? 创建一个N1?N1 的概率矩阵P1 ? 计算k次克罗内克幂得到Pk

? 对于每一个Pk的puv包括一个概率为puv的边（u,v）

关于采样

对于图的一些属性，已经有了很多算法进行计算，例如最短路径、中心算法等。但是当图大到一定程度时，这些算法因代价太高而变得不再实用。因此，对于给定的一个大的有向目标图，采样得到一个与原图有相似性质的样图是十分必要的。用什么方法进行采样，是随机取点，还是随机取边？样图的大小多少合适？怎么来评价一个样图的优劣，怎么来评价采样方法的优劣？这些是需要解决的问题。对于最后一个评价问题，我们需要考虑两个方面：

第一，评价的比较对象是什么？第二，我们想得到的采样图是要有与原图相同的属性，还是要和原图回退到与样图大小一样时类似？对于第二点中的前者，我们称其为缩放目的，后者成为时光倒流目的。

接下来的问题就是定义我们需要关注的图的属性。这些属性或者说度数分布的形状应该是重尾的，而且直径要小，等等。我们的目的不是要找针对图的某一个属性（如，边数，直径）的采样程序和相应的无偏的估计量（比例法则），我们要找的是一个通用的采样方法，这种方法可以匹配图的一整套属性，而且运用这种方法得到的采样图能够用来仿真或是用来做更加复杂的实验。

我们得到的主要结果如下：

? 我们提出了采样的中的两个不同的目标： 回退目标和缩放目标。 ? 对于上述的两个目标，我们对已发表的相关文献进行了彻底的分析和比较，测试了

多个采样算法。

我们进行了采样算法的系统估计，介绍了非平凡统计估计方法（(the Kolmogorov-Smirnov D-statistic and random walk inspired ideas），这种方法已经超出了简单的目测。

对于满足缩放目的的采样，基于随机走步的方法是运行最好的，因为它们是有偏的朝度数高的结点移动，并且得到的图是连通的。对于满足回退目的的采样，我们发现森林火灾类型的采样和基于结点的PageRank得分的采样运行的最好。这些算法是无偏的，因此能够很好的模拟图的时序演进。

推荐网络

我们致力于

? 在一个大规模的、真实的推荐网络中找到一个细粒度的影响模式 ? 给出谁影响谁的图 ? 找出级联(cascade)路径

? 检查网络的拓扑结构找出：

√ 什么样的级联在现实生活中频繁出现？ √ 它们是树状，星型，还是别的？

√ 级联尺寸的分布是什么样的（是同样大小，还是指数尾，或者是重尾）？ 我们通过以下步骤来进行工作： ? 找一个推荐网络数据集 ? 提出方法

√标示级联

分别为每个产品创建一张图。

删除最近的推荐信息：删除第一次购买该产品后的推荐信息。 删除没有购买的结点 √枚举级联 √计数级联

传感网络和P2P网络中信息的生存阈值

摘要：

本文考察传感网，P2P网或者是蓝牙手机通讯网。在这些网中，结点能相互传递信息，而且链路和结点能够增加或减少。本文也考察信息，例如一个传感网中的应急情况的一份报

告，一首民族传统歌曲或者是一个手机病毒。结点之间多长时间传递一次信息才能保证该信息能够存活（或者，在有病毒的情况下，什么条件能够使病毒失活）？显然，链路和结点的故障率是很重要的，但是还有别的什么能够确保数据的存活？

我们运用非线性动态系统和不动点的稳定性理论来解决这个问题。我们提供了一个闭合解，有一点令人惊讶，这个闭合解仅仅依赖一个额外的参数——连通矩阵的最大特征值。我们阐明了我们的分析在现实场景中的准确性，例如Intel 和 MIT的遥感网络，Gnutella网络和P2P网络。

网络媒体信息扩散路径的结构和动态研究

信息扩散、谣言和传染病的传播都是发生在一个潜在网络路径上的随机过程实例。通过观察传染病扩散网络就会发现，这种网络是随着时间动态变化的，因此，根据信息扩散的数据去推测动态网络是个值得研究的问题。假设信息在网络中扩散的路径是不可见的，只能根据传播后的结果来推测潜在网络的结构及其包含的路径，我们开发出了依赖于随机凸优化的在线算法，可以有效的解决动态网络推理问题。我们将算法应用于330万家主流媒体和博客网站，检验了它们一年中传播的超过1亿7900万条信息，得到了一些有趣的结论，在网络中一般的经常性主题消息的传播路径比持续的新闻消息的传播路径随着时间推移更加稳定，在一个新闻事件持续的几天内，媒体网站会出现集群现象但很快又会消失，主要的社会事件发生后，诸如利比亚内战，叙利亚冲突，会导致信息扩散路径的大量增长和网络媒体及博客的中心性总体上升。 具体的算法如下：

ktc其中k表示第k条消息，ic表示消息ck传到第

i个节点的时间，?i,j为第i个节点

与第

j个节点之间的传送频率，k为迭代次数

实验结果如下图所示

其中红色节点为媒体网站，蓝色节点为博客，不难发现证实了节点集群现象。

应用程序的例子：

agmfit:通过对给定的网络进行最大似然估计来拟合关系图模型(AGM)，得到网络

社区。

agmgen:实现了关系图模型(AGM)。AGM从社区关系的节点中产生一个图。 bigclam:制定社区检测问题转化为非负矩阵因子分解和发现社区成员节点的因素。

Cascades:在网上模拟一个SI模型，来计算级联结构的属性

Centrality:计算节点的中心性对策的图表：亲近，特征，程度，介，网页排名，集线器和当局。

Cliques:基于Clique Percolation Method，在网中找到重叠密集区的点， Girvan-Newman and Clauset-Newman-Moore Community:实现网络社区检测算法：

Concomp:计算一个图的最弱连通图，最强连通图和双连通图，以及割点

（articulation points ）和桥（若去掉一条边，便会使得整个图不连通，该边称为桥（bridge edges））。 Forestfire:用Forest Fire Modle产生图 Graphgen:用SNAP的许多产生器生成一个无向图

Graphhash:演示如何使用TGHash图的哈希表，用来计算的小的子图或信息级联频率。

Infopath:实现从级联数据的动态网络推理的随机算法，具体参见：Structure and

Dynamics of Information Pathways in On-Line Media Kcores:

应用程序的例子：

agmfit:通过对给定的网络进行最大似然估计来拟合关系图模型(AGM)，得到网络

社区。

agmgen:实现了关系图模型(AGM)。AGM从社区关系的节点中产生一个图。 bigclam:制定社区检测问题转化为非负矩阵因子分解和发现社区成员节点的因素。

Cascades:在网上模拟一个SI模型，来计算级联结构的属性

Centrality:计算节点的中心性对策的图表：亲近，特征，程度，介，网页排名，集线器和当局。

Cliques:基于Clique Percolation Method，在网中找到重叠密集区的点， Girvan-Newman and Clauset-Newman-Moore Community:实现网络社区检测算法：

Concomp:计算一个图的最弱连通图，最强连通图和双连通图，以及割点

（articulation points ）和桥（若去掉一条边，便会使得整个图不连通，该边称为桥（bridge edges））。 Forestfire:用Forest Fire Modle产生图 Graphgen:用SNAP的许多产生器生成一个无向图

Graphhash:演示如何使用TGHash图的哈希表，用来计算的小的子图或信息级联频率。

Infopath:实现从级联数据的动态网络推理的随机算法，具体参见：Structure and

Dynamics of Information Pathways in On-Line Media Kcores:

本文来源：https://www.bwwdw.com/article/raip.html