Python数据科学入门
Dmitry Zinoviev著
熊子源 译
第7章 使用网络数据
第38单元 概念剖析
图的元素、类型和密度：
| 名词 | 说明 |
|---|---|
| 多图 | 图中存在平行边（节点A可以通过多条边连接到节点B） |
| 循环 | 节点A到节点A的边 |
| 简单图 | 不存在平行边和循环的图 |
边中可以存在多种类型：
权重、数字、布尔和字符串类型的变量。
图的密度：
图与完全图的接近程度。一个具有e条边的n个节点的有向图，其密度为：
d = e/[n(n-1)]
。相应的无向图密度为：
d = 2e/[n(n-1)]
图的结构：
| 名词 | 说明 |
|---|---|
| 连通分量 | 集合中的每个节点都具有到达集合中的所有其他节点的路径（一组节点的集合） |
| GCC（巨型连通分量） | 最大的连通分量 |
| 桥 | 移除这条单边后图就会被分开的边 |
| 团 | 每个节点都与集合中的其他节点 直接 相连（一组节点的集合） |
| 最大团 | 图中最大的团 |
| 极大团 | 一个团不能通过向其中添加另一个节点而扩大（最大团一定是极大团；极大团不一定是最大团） |
| 星形图 | 集合中存在一个节点与其他所有节点相连接，但是其他节点之间不存在连接 |
| 领域 | 直接与节点A相连接的节点（G(A)） |
中心性：
-
度中心性
节点A的度中心性是A的邻居节点个数 -
接近中心性
节点A的接近中心性是其他所有节点到节点A的平均最短路径长度LBA的倒数：
-
中介中心性
节点A的中介中心性是指：所有两个节点之间的最短路径中，经过A点的路径数量与最短路径总数量之比 -
特征矢量中心性
节点A的特征矢量中心性被定义为：A的所有邻居节点的特征矢量中心性的加权和：
第39单元 网络分析序列
典型的网络分析序列包含以下几个步骤：
- 识别离散实体以及实体之间的关系。实体转化为网络节点，实体之间的关系转化为网络节点的边；
- 计算各种网络度量。密度，分量，GCC的大小，中心性等；
- 识别网络社区；
- 对结果进行解释，并生成一个报告。
第40单元 使用networkx
探索和分析网络：
NetworKit：
一种高效的、可并行化的网络分析工具包。可以与matplotlib,scipy,numpy,pandas和networkx相结合，进一步增加了这个模块的吸引力。详细内容可以参考官网：https://pypi.org/project/networkit/
Gephi：
各种网络和复杂系统的交互式可视化探索平台。详细内容可以参考官网：https://gephi.org/
团和社区结构：
find_cliques()
检测出图中最大的团（不能直接用于有向图）
isolates()
检测图中的孤立节点
best_partition()
使用Louvain方法并返回社区的划分结果，划分结果是一个以节点标签作为索引的字典，并用不同的数字序号区分不同的社区
Modularity()
给出社区的模块度（来判断网络结构是否清晰（0.5））
输入和输出：
| 类型 | 读 | 写 | 文件后缀 |
|---|---|---|---|
| 邻接列表 | read_adjlist(f) | write_adjlist(G,f) | 无特定后缀 |
| Edge list | read_edgelist(f) | write_edgelist(G,f) | 无特定后缀 |
| GML | read_gml(f) | write_gml(G,f) | .gml |
| GraphML | read_graphml(f) | write_graphml(G,f) | .graphml |
| Pajek | read_pajek(f) | write_pajek(G,f) | .net |
（
"Every mountain is unclimbable until someone climbs it."--《Downton Abbey》
）
