使用gephi-toolkit分析复杂网络

  1. 1. 基本介绍
    1. 1.1 gephi简介
    2. 1.2 gephi-toolkit简介
    3. 1.3 生成效果示例
  2. 2. 基本使用
    1. 2.1 生成原始gexf文件
      1. 2.1.1 基本数据列表定义赋值
      2. 2.1.2 创建点和线并导出原始gexf文件
    2. 2.2 运行社区模块化算法
      1. 2.2.1 导入原始gexf文件
      2. 2.2.2 将导入数据附加到 Graph API
      3. 2.2.3 运行社区模块化算法
      4. 2.2.4 运行布局算法优化样式
      5. 2.2.5 设置展现形式并导出
    3. 2.3 计算中介中心性和特征向量中心性
      1. 2.3.1 导入运行过社区模块化算法的gexf文件
      2. 2.3.2 计算中介中心性和特征向量中心性
  3. 3. 参考资料

1. 基本介绍

1.1 gephi简介

Gephi是一款开源免费跨平台基于JVM的复杂网络分析软件,其主要用于各种网络和复杂系统,动态和分层图的交互可视化与探测开源工具。

Gephi官网:https://gephi.org/developers/

1.2 gephi-toolkit简介

Gephi Toolkit是一个标准的java类库,任何java工程都可以引入使用,该类库中包含了Gephi中必要的模块,如Graph、Layout、Filters、IO等。 该工具包可以在java应用中使用,其保留了Gephi的绝大部分特性。

项目地址:https://github.com/gephi/gephi-toolkit

API文档:https://gephi.org/gephi/0.9.2/apidocs/

教程下载:https://gephi.org/tutorials/gephi-tutorial-toolkit.pdf

使用示例:https://github.com/gephi/gephi-toolkit-demos

意见建议:gephi-toolkit的功能基本上与gephi软件是对应的,可参照该软件上的功能描述看API文档。

存在的坑:

[1] 官方提供的Maven版gephi-toolkit不可用(亲测用不了,Github issues里有人也提出了这个不可用),但离线jar包可用。

1
2
3
4
5
6
<!-- 官方提供的,不可用-->
<dependency>
<groupId>org.gephi</groupId>
<artifactId>gephi-toolkit</artifactId>
<version>0.9.2</version>
</dependency>

[2] 除了gephi-toolkit的jar包之外,还需要一个生成gexf的工具依赖,这个依赖的官方Maven也是不可用,但离线jar包可用。

1
2
3
4
5
6
<!-- 官方提供的,不可用-->
<dependency>
<groupId>it.uniroma1.dis.wsngroup.gexf4j</groupId>
<artifactId>gexf4j</artifactId>
<version>1.0.0</version>
</dependency>

[3] 建议将本地jar配置到 pom.xml 文件里,而不是在“File——Project Structure——Libraries”里配置,后者虽然开发时能用,但打包的时候不会将其打进去。将本地jar配置到Maven里去的方法如下:

Step1:在项目根目录里建一个libs文件夹,将本地jar放进去。

Step2:pom.xml 文件里加上 scope 和 systemPath 即可。其中 ${project.basedir} 是Maven内置属性,表示项目根目录(即包含pom.xml文件的目录),可以直接使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<dependency>
<groupId>org.gephi</groupId>
<artifactId>gephi-toolkit</artifactId>
<version>0.9.2</version>
<scope>system</scope>
<systemPath>${project.basedir}/libs/gephi-toolkit-0.9.2-all.jar</systemPath>
</dependency>
<dependency>
<groupId>it.uniroma1.dis.wsngroup.gexf4j</groupId>
<artifactId>gexf4j</artifactId>
<version>1.0.0</version>
<scope>system</scope>
<systemPath>${project.basedir}/libs/gexf4j-1.0.0.jar</systemPath>
</dependency>

1.3 生成效果示例

Github上有开源的gexf渲染解析库,可以把生成的gexf通过Web前端进行展现,以下是展示效果:

Gephi生成效果示例

2. 基本使用

如工具类缺失,请从 https://github.com/gephi/gephi-toolkit-demos/tree/master/src/main/java/org/gephi/toolkit/demos/plugins/preview 里下载所需要的即可。

2.1 生成原始gexf文件

生成原始gexf需要点和边的基本数据列表,建议位置对应起来,原始gexf文件只有点和边的基本信息。

2.1.1 基本数据列表定义赋值

1
2
3
4
5
6
7
8
9
10
11
12
    // 定义gexf文件路径
String basePath = "d:/tmp/";
String tempGexfPath = basePath + StrUtil.format("{}.gexf", IdUtil.simpleUUID());
// 定义点的数据列表(赋值略)
List<String> pointIdList = new ArrayList<>();
List<String> pointLabelList = new ArrayList<>();
List<Integer> pointWeightList = new ArrayList<>();
// 定义边的数据列表(赋值略)
List<String> edgeIdList = new ArrayList<>();
List<Float> edgeWeightList = new ArrayList<>();
List<String> edgeSourceList = new ArrayList<>();
List<String> edgeTargetList = new ArrayList<>();

可通过Google Guava的HashBasedTable类库来遍历赋值,它相当于两个key的Map的数据结构,下面为基本使用示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import com.google.common.collect.HashBasedTable;
import com.google.common.collect.Table;

// 创建
Table<String, String, Float> weightTable = HashBasedTable.create();

// 新增
weightTable.put("aaa", "bbb", 1.0f);
weightTable.put("ccc", "ddd", 2.0f);
weightTable.put("ddd", "eee", 3.0f);

// 获取
float weight = weightTable.get("aaa", "bbb");

// 包含
boolean exist = weightTable.contains("aaa", "bbb")

// 遍历
Set<Table.Cell<String,String,String>> tableSet = weightTable.cellSet();
Iterator<Table.Cell<String,String,String>> it = tableSet.iterator();
while (it.hasNext()){
Table.Cell<String,String,String> data = it.next();
String rowCompany = data.getRowKey();
String columnId = data.getColumnKey();
float valueName = data.getValue();
System.out.println("行号:"+rowCompany+",列号:"+columnId+",值:"+valueName);
}

2.1.2 创建点和线并导出原始gexf文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 定义gexf文件
Gexf gexf = new GexfImpl();
Graph graph = gexf.getGraph();
AttributeList attrList = new AttributeListImpl(AttributeClass.NODE);
graph.getAttributeLists().add(attrList);
Attribute nodedef = attrList.createAttribute("0", AttributeType.STRING, "nodedef");
Attribute label = attrList.createAttribute("1", AttributeType.STRING, "label");
// 创建点
Map<String,Node> nodeMap = new HashMap<>();
Node node;
int pointLength = pointIdList.size();
for(int i=0; i<pointLength; i++){
node = graph.createNode(String.valueOf(i));
.setLabel(pointLabelList.get(i))
.getAttributeValues()
.addValue(nodedef, pointIdList.get(i))
.addValue(label, pointLabelList.get(i));
nodeMap.put(pointIdList.get(i),node);
}
// 创建线
int edgeLength = edgeIdList.size();
for(int i=0; i<edgeLength; i++){
try {
String uuid = edgeIdList.get(i);
String sourceNodeKey = edgeSourceList.get(i);
String targetNodeKey = edgeTargetList.get(i);
Node sourceNode = nodeMap.get(sourceNodeKey);
Node targetNode = nodeMap.get(targetNodeKey);
sourceNode.connectTo(uuid, targetNode).setWeight(edgeWeightList.get(i));
} catch (Exception e) {
continue;
}
}
// 生成gexf文件
StaxGraphWriter graphWriter = new StaxGraphWriter();
File f = new File(tempGexfPath);
Writer out;
try {
out = new FileWriter(f, false);
graphWriter.writeToStream(gexf, out, "UTF-8");
} catch (IOException e) {
e.printStackTrace();
}

2.2 运行社区模块化算法

Gephi提供社区探测算法对节点进行模块化,然后还提供多种布局算法,考虑到节点间的引力和斥力作用,完成自动美化功能,分割出一个个小社区。此时导出的gexf文件不光有点和边的基本信息,还有算法自动分配的颜色和位置等信息,也就决定了最终渲染出来的效果。

2.2.1 导入原始gexf文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 初始化一个项目
ProjectController pc = Lookup.getDefault().lookup(ProjectController.class);
pc.newProject();
Workspace workspace = pc.getCurrentWorkspace();
// 获取控制器和模型
ImportController importController = Lookup.getDefault().lookup(ImportController.class);
GraphModel graphModel = Lookup.getDefault().lookup(GraphController.class).getGraphModel();
AppearanceController appearanceController = Lookup.getDefault().lookup(AppearanceController.class);
AppearanceModel appearanceModel = appearanceController.getModel();
// 导入文件
Container container = null;
try {
File file = new File(tempGexfPath);
container = importController.importFile(file);
} catch (Exception ex) {
ex.printStackTrace();
}

2.2.2 将导入数据附加到 Graph API

第一种:将导入数据附加到Graph API

1
2
3
// 将全部导入数据附加到 Graph API        
importController.process(container, new DefaultProcessor(), workspace);
DirectedGraph newGraph = graphModel.getDirectedGraph();

第二种:将导入数据附加到Graph API,并按照条件过滤节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 将导入数据附加到 Graph API,并移除 degree <= 1 的孤立点
importController.process(container, new DefaultProcessor(), workspace);
FilterController filterController = Lookup.getDefault().lookup(FilterController.class);
DegreeRangeBuilder.DegreeRangeFilter degreeFilter = new DegreeRangeBuilder.DegreeRangeFilter();
degreeFilter.init(graphModel.getGraph());
degreeFilter.setRange(new Range(1, Integer.MAX_VALUE));
Query query = filterController.createQuery(degreeFilter);
GraphView view = filterController.filter(query);
graphModel.setVisibleView(view);
UndirectedGraph filterNewGraph = graphModel.getUndirectedGraphVisible();
int pointCount = filterNewGraph.getNodeCount(); // 过滤后点数量
int edgeCount = filterNewGraph.getEdgeCount(); // 过滤后线数量
System.out.println("Nodes: " + pointCount);
System.out.println("Edges: " + edgeCount);

2.2.3 运行社区模块化算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 运行社区模块化算法
Modularity modularity = new Modularity();
modularity.setUseWeight(true); // 是否使用权重:使用边的权重
modularity.setRandom(true); // 是否随机:产生更好的分解,但是会增加计算时间
modularity.setResolution(1.0); // 解析度:1.0是标准的解析度,数字越小,社区越多
modularity.execute(graphModel);
// 由模块化算法创建分类并设置颜色
Column modColumn = graphModel.getNodeTable().getColumn(Modularity.MODULARITY_CLASS);
Function func = appearanceModel.getNodeFunction(filterNewGraph, modColumn, PartitionElementColorTransformer.class);
Partition partition = ((PartitionFunction) func).getPartition();
int divisionCount = partition.size(); // 社区划分数量
System.out.println(divisionCount + " partitions found");
Palette palette = PaletteManager.getInstance().randomPalette(partition.size());
partition.setColors(palette.getColors());
appearanceController.transform(func);
// 分配节点大小:按中心性排序大小
Column centralityColumn = graphModel.getNodeTable().getColumn(Modularity.MODULARITY_CLASS);
Function centralityRanking = appearanceModel.getNodeFunction(filterNewGraph, centralityColumn, RankingNodeSizeTransformer.class);
RankingNodeSizeTransformer centralityTransformer = centralityRanking.getTransformer();
centralityTransformer.setMinSize(1);
centralityTransformer.setMaxSize(5);
appearanceController.transform(centralityRanking);

2.2.4 运行布局算法优化样式

Gephi支持大量的布局算法,可以优化样式。如何选择一个合适的算法、参数调整到多少合理是这里的难点,这块儿内容比较麻烦,迭代过程也比较慢,最终结果好不好看主要取决于此。以下我仅介绍三种布局算法,其余的自己看官方API文档即可。

第一种:ForceAtlas2布局算法

ForceAtlas2布局算法是一种力引导算法。 该算法整合了包括Barnes Hut近似,度决定性斥力,全局与局部迭代速度自适应调整等技术。 相比于Force Atlas算法,ForceAtlas2运行速度更快,并且处理的图的规模更大。 算法运行时,节点与节点之间将会相互排斥,存在连边的两个节点将会相互吸引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// ForceAtlas2布局算法         
ForceAtlas2 layout = new ForceAtlas2(null);
layout.setGraphModel(graphModel);
layout.resetPropertiesValues();
layout.setAdjustSizes(true); // 缩放
layout.setScalingRatio(2.0d); // 缩放比例
layout.setEdgeWeightInfluence(1.0d); // 边的权重的影响(你给多少影响到边的权重。0"没有影响”,1是“正常”)
layout.setGravity(1.0d); // 重力(吸引到中心节点。防止岛屿渐行渐远)
layout.setLinLogMode(true); // LinLog模式(切换ForceAtlas模型的线性-线性坐标系到线性-对数坐标系,使团块更紧凑)
layout.setStrongGravityMode(false); // 更强的重力(一个强有力的万有引力定律)
layout.setThreadsCount(256); // 线程数(如果你的内核可以处理更多的线程意味着更快的速度)
layout.initAlgo();
for (int i = 0; i < 10000 && layout.canAlgo(); i++) {
layout.goAlgo();
}
layout.endAlgo();

第二种:Fruchterman Reingold布局算法

FR算法建立在粒子物理理论的基础上,将图中的节点模拟成原子,通过模拟原子间的力场来计算节点间的位置关系。 算法通过考虑原子间引力和斥力的互相作用,计算得到节点的速度和加速度。 依照类似原子或者行星的运动规律,系统最终进入一种动态平衡状态。

1
2
3
4
5
6
7
8
9
10
11
// Fruchterman Reingold布局算法
FruchtermanReingold layout = new FruchtermanReingold(null);
layout.setGraphModel(graphModel);
layout.resetPropertiesValues();
layout.setArea(10000.0f); // 区域(图形大小面积)
layout.setGravity(10.0d); // 重力(这种力量吸引了所有节点的中心,以避免失连接部件的分散)
layout.setSpeed(1.0d); // 速度(以精度损失为代价,提高收敛速度)
layout.initAlgo();
for (int i = 0; i < 1000 && layout.canAlgo(); i++) {
layout.goAlgo();
}

注:该布局算法的迭代速度相比其他算法要慢很多。

第三种:YifanHuLayout布局算法

YifanHuLayout是一种将力导向算法和多级算法的优点结合在一起以降低算法复杂度的算法。这是一种非常适用于大型网络的算法。

1
2
3
4
5
6
7
8
9
10
11
12
// YifanHuLayout布局算法        
YifanHuLayout layout = new YifanHuLayout(null, new StepDisplacement(1f));
layout.setGraphModel(graphModel);
layout.resetPropertiesValues();
layout.setOptimalDistance(100.0f); // 设置最佳距离(弹簧自然长度,更大的值意味着节点将相距较远)
layout.setStep(10.0f); // 设置初始步长(在整合阶段的初始步长。将此值设置为一个有意义的大小,相比于最佳距离,10%是一个很好的起点)
layout.setStepRatio(0.95f); // 设置步比率(该比率用于更新各次迭代的步长)
layout.setAdaptiveCooling(true); // 设置自适应冷却(控制自适应冷却的使用。它是用来帮助布局算法以避免能量局部极小)
layout.initAlgo();
for (int i = 0; i < 10000 && layout.canAlgo(); i++) {
layout.goAlgo();
}

2.2.5 设置展现形式并导出

设置展现形式,

1
2
3
4
5
// 设置“显示标签”选项,并禁用节点大小对文本大小的影响
PreviewModel previewModel = Lookup.getDefault().lookup(PreviewController.class).getModel();
previewModel.getProperties().putValue(PreviewProperty.SHOW_NODE_LABELS, Boolean.TRUE); // 是否展示node_label
previewModel.getProperties().putValue(PreviewProperty.NODE_LABEL_PROPORTIONAL_SIZE, Boolean.FALSE); // 禁用节点大小对文本大小的影响
previewModel.getProperties().putValue(PreviewProperty.EDGE_CURVED, Boolean.FALSE); // 是否弯曲

导出gexf文件:

第一种:仅导出可见部分(那些在2.2.2节过滤掉的节点就没了)

1
2
3
4
5
6
7
8
9
10
11
12
// 导出gexf(仅导出可见部分)
String basePath = "d:/tmp/";
String gexfPath = basePath + StrUtil.format("{}.gexf", IdUtil.simpleUUID());
ExportController ec = Lookup.getDefault().lookup(ExportController.class);
GraphExporter exporter = (GraphExporter) ec.getExporter("gexf");
exporter.setExportVisible(true);
exporter.setWorkspace(workspace);
try {
ec.exportFile(new File(gexfPath), exporter);
} catch (IOException ex) {
ex.printStackTrace();
}

第二种:导出所有节点(那些在2.2.2节过滤掉的节点依然存在,因为那些节点没有参与处理,所以是原始颜色和原始大小)

1
2
3
4
5
6
7
8
9
10
11
// 导出gexf(导出所有节点)
String basePath = "d:/tmp/";
String gexfPath = basePath + StrUtil.format("{}.gexf", IdUtil.simpleUUID());
graphWriter = new StaxGraphWriter();
f = new File(gexfPath);
try {
out = new FileWriter(f, false);
graphWriter.writeToStream(gexf, out, "UTF-8");
} catch (IOException e) {
e.printStackTrace();
}

2.3 计算中介中心性和特征向量中心性

2.3.1 导入运行过社区模块化算法的gexf文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 初始化一个项目
pc = Lookup.getDefault().lookup(ProjectController.class);
pc.newProject();
workspace = pc.getCurrentWorkspace();
// 获取控制器和模型
importController = Lookup.getDefault().lookup(ImportController.class);
graphModel = Lookup.getDefault().lookup(GraphController.class).getGraphModel();
// 导入文件
try {
File file = new File(gexfPath);
container = importController.importFile(file);
} catch (Exception e) {
e.printStackTrace();
}
// 将导入数据附加到 Graph API
importController.process(container, new DefaultProcessor(), workspace);
UndirectedGraph finalGraph = graphModel.getUndirectedGraph();

2.3.2 计算中介中心性和特征向量中心性

中介中心性(betweenesscentrality):

在进行社会网络分析的过程中,如果对社区进行拆分,用户节点的中介中心性是会发生变化的,通过对多次测试实验结果分析发现,用户在社区内的中介中心性普遍高于在整个社会网络中的中介中心性,但社区内的讨论往往是基于某一类主题展开的,为了体现出该用户的影响力,还是需要考虑该节点对整个社会网络的中介作用,因此研究选择用户节点在整个社会网络中的中介中心性用于进行节点影响力计算。

特征向量中心性(eigenvectorcentrality):

特征向量中心性综合考虑了用户节点在整个社会网络中的位置和其对应的影响力,即如果该用户节点对应的“联系人”越多,则说明该节点越处于社会网络的中心位置。

工具方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public HashMap<org.gephi.graph.api.Node, Integer> createInvIndicesMap(org.gephi.graph.api.Graph graph) {
HashMap<org.gephi.graph.api.Node, Integer> newInvIndices = new HashMap<>();
int index = 0;
for (org.gephi.graph.api.Node s : graph.getNodes()) {
newInvIndices.put(s, index);
index++;
}
return newInvIndices;
}

public HashMap<Integer, org.gephi.graph.api.Node> createIndicesMap(org.gephi.graph.api.Graph graph) {
HashMap<Integer, org.gephi.graph.api.Node> newIndices = new HashMap<>();
int index = 0;
for (org.gephi.graph.api.Node s : graph.getNodes()) {
newIndices.put(index, s);
index++;
}
return newIndices;
}

计算部分的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 计算中介中心性和特征向量中心性
HashMap<org.gephi.graph.api.Node, Integer> invIndicies = this.createInvIndicesMap(finalGraph);
HashMap<Integer, org.gephi.graph.api.Node> indicies = this.createIndicesMap(finalGraph);
List<Double> betweenesscentralityList = new ArrayList();
// 中介中心性(betweenesscentrality)
GraphDistance distance = new GraphDistance();
Map<String, double[]> distanceMapResult = distance.calculateDistanceMetrics(finalGraph,invIndicies,false,true);
double[] betweenesscentrality = distanceMapResult.get("betweenesscentrality");
for (int i = 0; i < betweenesscentrality.length; i++) {
betweenesscentralityList.add(betweenesscentrality[i]);
}
// 计算特征向量中心性(eigenvectorcentrality)
int nodeLength = finalGraph.getNodeCount();
double[] eigCentralities = new double[nodeLength];
List<Double> eccentricityList = new ArrayList();
for (int i = 0; i < nodeLength; i++) {
eigCentralities[0]=pointWeightList.get(i);
// directed:是否有向,numlterations:迭代次数
EigenvectorCentrality eigenvectorCentrality = new EigenvectorCentrality();
double eigenvectorCentralityVal = eigenvectorCentrality.calculateEigenvectorCentrality(finalGraph,eigCentralities,
indicies,invIndicies,false,100);
eccentricityList.add(eigenvectorCentralityVal);
}

3. 参考资料

[1] 复杂网络社团发现,Gephi绘制网络图 from CSDN

[2] FR算法(Fruchterman-Reingold) from Dyleaf

[3] Gephi简易学习,拓展分析红楼梦数据 from 程序员的秘密

[4] Gephi功能介绍及网络可视化案例 from segmentfault

[5] Gephi教程:Gephi 基本使用 from 咻咻ing

[6] 度中心性、介数中心性、特征向量中心性 from 言非の博客