如何处理gexf文件？

版权所有2008-2010 Gephi的

作者：马修Bastian <mathieu.bastian@gephi.org>的

网址：http://www.gephi.org的

此文件属于Gephi。

Gephi是自由软件：您可以重新分配和/或修改

根据GNU Affero通用公共许可证的条款

自由软件基金会，无论是第3版的出版

许可证，或瞎核败（在你的选项）任何更新的版本。

Gephi分布在希望，这将是有用的，

但没有任何担保，甚至没有隐含的担保

适销性或针对特定用途的适用性。请参阅

GNU Affero通用公共许可证的更多细节。

您应该已经收到GNU Affero通用公共许可证的副本

随着Gephi。如果没有看到<http://www.gnu.org/licenses/>。

* /

包org.gephi.toolkit.demos

进口的java.io.File

进口java.io.IOException异常

导入java.util.concurrent.TimeUnit

进口org.gephi.graph.api.DirectedGraph

进口org.gephi.graph.api.GraphController

导入org.gephi.graph.api.GraphModel

进口氏皮org.gephi.io.exporter.api.ExportController

进口org.gephi.io.importer.api.Container

导入org.gephi.io.importer.api.EdgeDefault

进口org.gephi.io.importer.api.ImportController

导入org.gephi.io.processor.plugin.DefaultProcessor

导入org.gephi.layout.plugin.AutoLayout

导入org.gephi.layout.plugin.force.StepDisplacement

导入org.gephi.layout.plugin.force.yifanHu.YifanHuLayout

导入org.gephi.layout.plugin.forceAtlas.ForceAtlasLayout

进口org.gephi.project.api.ProjectController

导入org.gephi.project.api.Workspace

导入org.openide.util.Lookup

/ **

*本演示展示了如何使用的<code>自动版式</ code>类运行布局

*编程。

* <P>

*您可以设置一个的布局持续时间，比几个布局和执行。为

*比如你设置0.8为胡一帆算法和0.2标签调整。如果

*执行时间为100秒，则80秒的第一算法运行和

*秒20秒。它还允许磨颤动态改变属性值

*（按一定比例或内插，如果值是数值）。

*

* @作者马修巴斯蒂安

* /

公共 类 WithAutoLayout {

公共 无效 脚本（）{

/ /初始化一个项目 - 工作区

/ /һĿ - һ

ProjectController PC = Lookup.getDefault（）。查找（ProjectController.类）

pc.newProject（）

工作区工作区= pc.getCurrentWorkspace（）

/ /附加容器图形结构

/ /图像νṹ

ImportController importController = Lookup.getDefault（）。查找（ImportController. 类）

/ /导入文件

/ / L

集装箱容器

尝试 {

档案文件

容器：= importController.importFile（文件）

container.getLoader（）。setEdgeDefault（EdgeDefault.DIRECTED） / /力

（container.setAllowAutoNode / /不要创建缺少的节点

} 赶上 （例外）{

ex.printStackTrace（）

返回

}

importController.process（容器，的新 DefaultProcessor（），工作区）

/ /查看图以及进口

/ /ͼ

而GraphModel而GraphModel = Lookup.getDefault（）。查找（GraphController. 类）。getModel（）

的DirectedGraph图= graphModel.getDirectedGraph（）

（ I = 1 <= graph.getNodeCount（）+ +）{

/ /（“节点：”+ graph.getNode（I）。getNodeData（））

}

（“边缘：” + graph.getEdgeCount（））

/ /布局1分钟

/ / 1

/ / ^ ^

长 = 0

如果 （graph.getEdgeCount（）>20000 ）{

时间=（长）（（（双）graph.getEdgeCount（）/ 80 ））

/ /（“日志：黄正：”+ DateUtil.time2str（（int）的System.currentTimeMillis的（），“YYYY-MM-DD HH：MM：SS”）+“当前<STRONG>生成</ >图像所花费的时间：“+时间）

其他

（graph.getEdgeCount（）>12000 ）{

时间=（长）（（（双）graph.getEdgeCount（）/ 85 ））

/ /（“日志：黄正：”+ DateUtil.time2str（（int）的System.currentTimeMillis的（），“YYYY-MM-DD HH：MM：SS”）+“当前<STRONG>生成</ >图像所花费的时间：“+时间）

否则 ，如果 （graph.getEdgeCount（）>8000 ）{

时间=（长）（（（双）graph.getEdgeCount（）/ 90 ））

/ /（“日志：黄正：”+ DateUtil.time2str（（int）的System.currentTimeMillis的（），“YYYY-MM-DD HH：MM：SS”）+“当前<STRONG>生成</ >图像所花费的时间：“+时间）

其他 （graph.getEdgeCount（）>5000 ）{

时间=（长）（（（双）graph.getEdgeCount（）/ 95 ））

/ /（“日志：黄正：”+ DateUtil.time2str（（int）的System.currentTimeMillis的（），“YYYY-MM-DD HH：MM：SS”）+“当前<STRONG>生成</ >图像所花费的时间：“+时间）

否则 ，如果 （graph.getEdgeCount（）>100 ）{

时间=（长）（（（双）graph.getEdgeCount（）/ 100 ））

/ /（“日志：黄正：”+ DateUtil.time2str（（int）的System.currentTimeMillis的（），“YYYY-MM-DD HH：MM：SS”）+“当前<STRONG>生成</ >图像所花费的时间：“+时间）

其他 {

时间= 1

}

自动版式自动版式= 新的 自动版式（时间，TimeUnit.SECONDS）

autoLayout.setGraphModel（而GraphModel）

YifanHuLayout secondLayout = 新 YifanHuLayout（空，新StepDisplacement（3420））

ForceAtlasLayout firstLayout =：新 ForceAtlasLayout（空）

AutoLayout.DynamicProperty adjustBySizeProperty = AutoLayout.createDynamicProperty（的“forceAtlas.adjustSizes.name” ，Boolean.TRUE，0 .1 F）/ /真后，10％的布局时间

AutoLayout.DynamicProperty repulsionProperty = AutoLayout.createDynamicProperty（的“forceAtlas.repulsionStrength.name” ，新的双（500 ），0F）/ / 500的完整周期

autoLayout.addLayout（firstLayout，0 .5楼新 AutoLayout.DynamicProperty [] {adjustBySizeProperty，repulsionProperty}）

autoLayout.addLayout（secondLayout，0 .5 F）

autoLayout.execute（）

/ / ^ ^

/ /导出

ExportController EC = Lookup.getDefault（）。查找（ExportController.类）

尝试 {

ec.exportFile（新的 文件（“WebRoot/WEB-INF/weiboGexf/io_gexf2.gexf” ））

} 渔获 （IOException异常前）{

ex.printStackTrace（）

}

}

公共 静态 无效的 主要（字串[] args）{

WithAutoLayout的autoLayout =的新 WithAutoLayout（）

autoLayout.script（）

/ /的System.out.println（）

}

}

通过一个综合数据分析案例：”金庸的江湖——金庸武侠小说中的人物关系挖掘“，来学习和掌握MapReduce程序设计。通过本项目的学习，可以体会如何使用MapReduce完成一个综合性的数据挖掘任务，包括全流程的数据预处理、数据分析、数据后处理等。

1 任务1 数据预处理

1.1 任务描述

从原始的金庸小说文本中，抽取出与人物互动相关的数据，而屏蔽掉与人物关系无关的文本内容，为后面的基于人物共现的分析做准备。

1.2 关键问题

1.2.1 中文分词和人名提取

使用开源的Ansj_seg进行分词。Ansj_seg不仅支持中文分词，还允许用户自定义词典，在分词前，将人名列表到添加用户自定义的词典，可以精确识别金庸武侠小说中的人名。

但实际测试的时候发现，Ansj_seg分词会出现严重的歧义问题，比如“汉子”属于人名列表中的人名(nr)，但Ansj_seg可能会错误地将它分类为名词(n)。因此，如果根据词性提取人名，会导致最后提取的人名太少。解决方法是在提取人名的时候，需要在将人名加入用户自定义词典的同时，构造一个包含所有人名的字典，对分词的结果逐个进行测试，如果在字典里，就是人名。

1.2.2 文件传输

使用HDFS传递数据。考虑到人名列表文件已经存放在了HDFS里，所以使用HDFS的方式不需要移动人名列表文件，只需要在Configuration中设置文件在HDFS文件系统中的路径，然后在Mapper的setup()函数里调用HDFS的函数获取文件内容即可。

1.2.3 单词同现算法

两个单词近邻关系的定义：实验要求中已经说明，同现关系为一个段落。

段落划分：非常庆幸的是，小说原文中一个段落就是一行，因此，不需要自己定义FileInputFormat和RecordReader。

1.3 MapReduce设计

1.3.1 Mapper

1.3.2 Reducer

1.3.3 Driver

2 任务2 特征抽取：人物同现统计

2.1 任务描述

完成基于单词同现算法的人物同现统计。在人物同现分析中，如果两个人在原文的同一段落中困嫌出现，则认为两个人发生了一次同现关系。我们需要对人物之间的同现关系次数进行统计，同现关系次数越多，则说明两人的关系越密切。

2.2 关键问题

2.2.1 人名冗余

在同一段中，人名可能多次出现，任务一只负责提取出所有的人名，没有剔除多余的人名，任务必须在输出同现次数之前汪简手处理冗余人名。我的做法是在Mapper中创建一个集合，把所有人名放入集合中，集合会自动剔除冗余的人名。

2.2.2 同现次数统计

两个人物之间应该输出两个键值对，如“狄云”和“戚芳”，应该输出“<狄云，戚芳>1”和“<戚芳，狄云>1”。多个段落中允许输出相同的键值对，因此，Reducer中需要整合具有相同键的输出，输出总的同现次数。

2.3 MapReduce设计

2.3.1 Mapper

2.3.2 Reducer

3 任务3 特征处理：人物关系图构建与特征归一化

3.1 任务描述

根据任务2人物之间的共现关系，生成人物之间的关系图。人物关系使用邻接表的形式表示，人物是顶点，人物之间关系是边，两个人的关系的密切程度由共现次数体现，共现次数越高，边权重越高。另外需要对共现次数进行归一化处理，确保某个顶点的出边权重和为1。

3.2 关键问题

3.2.1 确保人物的咐携所有邻居输出到相同结点处理

在Mapper结点将输入的键值对“<狄云，戚芳>1”拆分，输出新的键值对“<狄云>戚芳:1”，“狄云”的所有邻居会被分配给同一个Reducer结点处理。

3.2.2 归一化

在Reducer结点首先统计该人物与所有邻居同现的次数和sum，每个邻居的的同现次数除以sum就得到共现概率。为了提高效率，在第一次遍历邻居的时候，可以把名字和共现次数保存在链表里，避免重复处理字符串。

3.3 MapReduce设计

3.3.1 Mapper

3.3.2 Reducer

4.1 任务描述

经过数据预处理并获得任务的关系图之后，就可以对人物关系图作数据分析，其中一个典型的分析任务是：PageRank 值计算。通过计算 PageRank，我们就可以定量地获知金庸武侠江湖中的“主角”们是哪些。

4.2 PageRank原理

PageRank算法由Google的两位创始人佩奇和布林在研究网页排序问题时提出，其核心思想是：如果一个网页被很多其它网页链接到，说明这个网页很重要，它的PageRank值也会相应较高；如果一个PageRank值很高的网页链接到另外某个网页，那么那个网页的PageRank值也会相应地提高。

相应地，PageRank算法应用到人物关系图上可以这么理解：如果一个人物与多个人物存在关系连接，说明这个人物是重要的，其PageRank值响应也会较高；如果一个PageRank值很高的人物与另外一个人物之间有关系连接，那么那个人物的PageRank值也会相应地提高。一个人物的PageRank值越高，他就越可能是小说中的主角。

PageRank有两个比较常用的模型：简单模型和随机浏览模型。由于本次设计考虑的是人物关系而不是网页跳转，因此简单模型比较合适。简单模型的计算公式如下，其中Bi为所有连接到人物i的集合，Lj为认为人物j对外连接边的总数：

在本次设计的任务3中，已经对每个人物的边权值进行归一化处理，边的权值可以看做是对应连接的人物占总边数的比例。设表示人物i在人物j所有边中所占的权重，则PageRank计算公式可以改写为：

4.3.2 PageRanklter类

GraphBuilder将数据处理成可供迭代的格式，PageRank的迭代过程由PageRanklter类实现，包含一个Map和Reduce过程。Map过程产生两种类型的<key,value>：<人物名，PageRrank值>，<人物名，关系链表>。第一个人物名是关系链表中的各个链出人物名，其PR值由计算得到；第二个人物名是本身人物名，目的是为了保存该人物的链出关系，以保证完成迭代过程。以上面的输出为例，则Map过程产生的键值对为<完颜萍, 1.0 0.005037>，<小龙女, 1.0 0.017632>，……，<一灯大师, #完颜萍:0.005037783……>。

Reduce过程将同一人物名的<key,value>汇聚在一起，如果value是PR值，则累加到sum变量；如果value是关系链表则保存为List。遍历完迭代器里所有的元素后输出键值对<人物名，sum#List>，这样就完成了一次迭代过程。

PR值排名不变的比例随迭代次数变化的关系图如下，由于我们考虑的是找出小说中的主角，所以只要关心PR值前100名的人物的排名的变化情况，可以看到迭代次数在10以后，PR值排名不变的比例已经趋于稳定了，所以基于效率考虑，选取10作为PR的迭代次数。

4.3.3 PageRankViewer类

当所有迭代都完成后，我们就可以对所有人物的PageRank值进行排序，该过程由PageRankViewer类完成，包含一个Map和Reduce过程。Map过程只提取迭代过程输出结果中的人物名以及对应的PageRank值，并以PageRank值作为key，人物名作为value输出。为了实现PageRank值从大到小排序，需要实现DescFloatComparator类来重写compare方法以达成逆序排序。由于可能存在PageRank值相同的情况，所以还需要一个reduce过程来把因PageRank值相同而汇聚到一起的人物名拆开并输出。

PageRankMapper

PageRankReducer

Driver类

5.1 任务描述

标签传播（Label Propagation）是一种半监督的图分析算法，他能为图上的顶点打标签，进行图顶点的聚类分析，从而在一张类似社交网络图中完成社区发现。在人物关系图中，通过标签传播算法可以将关联度比较大的人物分到同一标签，可以直观地分析人物间的关系。

5.2 标签传播算法原理

标签传播算法（Label Propagation Algorithm，后面简称LPA）是由Zhu等人于2002年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。LPA基本过程为：（1）每个结点初始化一个特定的标签值；（2）逐轮更新所有节点的标签，直到所有节点的标签不再发生变化为止。对于每一轮刷新，节点标签的刷新规则如下：对于某一个节点，考察其所有邻居节点的标签，并进行统计，将出现个数最多的那个标签赋值给当前节点。当个数最多的标签不唯一时，随机选择一个标签赋值给当前节点。

LPA与PageRank算法相似，同样需要通过迭代过程来完成。在标签传播算法中，节点的标签更新通常有同步更新和异步更新两种方法。同步更新是指，节点x在t时刻的更新是基于邻接节点在t-1时刻的标签。异步更新是指，节点x在t时刻更新时，其部分邻接节点是t时刻更新的标签，还有部分的邻接节点是t-1时刻更新的标签。若LPA算法在标签传播过程中采用的是同步更新，则在二分结构网络中，容易出现标签震荡的现象。在本次设计中，我们考虑到了两种更新方法，并进行了比较。

5.3 标签传播算法在mapreduce上的实现细节

5.3.1 LPAInit类

为实现LPA的迭代过程，需要先给每个人物赋予一个独特标签，标签初始化由LPAInit类完成，仅包含一个Map过程。标签由数字表示，Map过程由1开始，为每一个人物名赋予一个独特的标签。为了便于后面的可视化分析，我们需要把PageRank值和标签整合在一起，所以LPAInit的输入文件直接采用PageRank过程的输出文件，格式如下：

5.3.2 LPAIteration类

LPAIteration类完成标签的更新过程，其格式与LPAInit的输出格式一致，包含一个Map和Reduce过程。Map过程对输入的每一行进行切割，输出四种格式的<key,value>：<人物名，关系链表>，<人物名，PageRank值>，<人物名，标签>，<链出人物名，标签#起点人物名>。第四种格式个键值对是为了将该节点的标签传给其所有邻居。

Reduce过程对value值进行识别，识别可以通过Map过程把预先定义好的特殊字符如‘#’、‘@’来实现前缀到value上来实现。由于人物关系图中的各个边都是有权重的，并且代表两个人物的相关程度，所以标签更新过程不是用边数最多的标签而是权重最大标签来更新，我们可以预先把权重最大的若干个保存到一个链表中，如果存在多个权重相同的标签，则随机选取一个作为该人名新的标签。异步方法更新标签需要使用一个哈希表来存储已经更新标签的人物名和它们的新标签，并且在更新标签时使用该哈希表里面的标签。同步方法更新标签则不需要存储已更新的标签。

本次设计中比较了同步和异步更新两种方法，下图为标签不变的比例随迭代次数的变化。可以发现，异步收敛速度更快，只要6次迭代即可完全收敛，且标签不变的比例可达100%。而同步更新方法则不能达到100%，说明人物关系图中存在子图是二部子图。

5.3.3 LPAReorganize类

LPA算法迭代收敛后，所有人物名的标签不再变化，但是此时的标签排列是散乱的，需要把同一标签的人物名整合在一起。该过程由LPAReorganize类完成，包含一个Map和Reduce过程。Map过程对输入的每一行进行切割，以<标签，人物名#PageRank值#关系链表>格式输出。Reduce过程中，同一标签的人物名汇聚在一起，然后根据每个标签人物集合的大小从大到小排序，重新赋予标签（从1开始）。这样输出文件中同一标签的人物名就会聚集在一起。最后的输出格式如下：

5.3.2 LPAMapper类

LPAIteration类完成标签的更新过程，其格式与LPAInit的输出格式一致，包含一个Map和Reduce过程。Map过程对输入的每一行进行切割，输出四种格式的<key,value>：<人物名，关系链表>，<人物名，PageRank值>，<人物名，标签>，<链出人物名，标签#起点人物名>。第四种格式个键值对是为了将该节点的标签传给其所有邻居。

5.3.2 LPAReducer类

Reduce过程对value值进行识别，识别可以通过Map过程把预先定义好的特殊字符如‘#’、‘@’来实现前缀到value上来实现。由于人物关系图中的各个边都是有权重的，并且代表两个人物的相关程度，所以标签更新过程不是用边数最多的标签而是权重最大标签来更新，我们可以预先把权重最大的若干个保存到一个链表中，如果存在多个权重相同的标签，则随机选取一个作为该人名新的标签。异步方法更新标签需要使用一个哈希表来存储已经更新标签的人物名和它们的新标签，并且在更新标签时使用该哈希表里面的标签。同步方法更新标签则不需要存储已更新的标签。

Driver类

6.1 可视化工具Gephi

Gephi是一款开源的跨平台的基于JVM的复杂网络分析软件。把PageRank和LPA的结果，转化为gexf格式，在Gephi中绘制图像并分析大数据实验结果，更加直观、易于理解。

gexf实际上是一种特殊的XML文件，python的gexf库提供了接口方便我们编辑和生成gexf文件，因此我们选择使用python处理PageRank和LPA的结果。顶点有两种属性，LPA生成的标签和PageRank计算的PR值，每条边的权重是PageRank计算出的值。在可视化的时候，标签决定顶点显示的颜色，PR值决定标签的

6.2 可视化预处理

编写一个python程序transform2xml.py，将数据分析部分得到的PR值，标签以及点连接关系处理成一个可供Gephi读取的gexf文件。

6.3 可视化结果

7 输出结果截图

7.2 同现次数统计

7.4 PageRank

---