0. 前言

社交网站的崛起是近年来数字媒体领域最活跃的发展趋势之一，数字社交互动已经融入人们的日常生活中。社交网络中，用户既能分享观点、发布动态与反馈、参与线上活动，又能在社交平台上展示广泛的生活兴趣。
此外，社交网络为研究用户行为、解读人际互动及预测兴趣偏好提供了海量数据资源。将其构建为图结构(顶点代表人，边代表连接关系)，便形成了提取有效信息的强大工具。然而，由于涉及大量可变参数，理解驱动社交网络演变的动态机制是一个复杂问题。
本节将探讨如何运用图论分析社交网络，并通过机器学习解决链接预测和社区发现等实际问题。

1. 数据集分析

本节将使用 SNAP Facebook 公共数据集。该数据集通过收集调查参与者的 Facebook 用户信息创建，包含 10 位用户的自我网络 (ego network)。每位用户需标注其好友所属的社交圈子，平均每位用户标注了 19 个社交圈，每个圈子平均包含 22 位好友。针对每位用户，数据集收集了以下信息：

• 边关系：若两位用户在 Facebook 互为好友则存在边连接
• 节点特征：用户个人资料若具备某项特征则标记为 1，否则为 0。

最终将这 10 个自我网络合并为统一图结构供研究使用。

1.1 数据集介绍

数据集主要包含三个可下载文件：facebook.tar.gz、facebook_combined.txt.gz 和 readme-Ego.txt。各文件说明如下：

• facebook.tar.gz：包含每个 ego 用户的四个文件(共 40 个文件)。文命名格式为 nodeId.extension，其中 nodeId 表示 ego 用户节点 ID，extension 包括 edges、circles、feat、egofeat 或 featnames：
  • nodeId.edges：包含 nodeId 节点网络的边列表
  • nodeId.circles：包含多行记录(每行对应一个社交圈)，每行由圈子名称和系列节点 ID 组成
  • nodeId.feat：记录自我中心网络中所有节点的特征( 0 表示 nodeId 具备该特征，1 则相反)
  • nodeId.egofeat：包含 ego 用户的特征
  • nodeId.featname：保存特征名称列表
• facebook_combined.txt.gz：包含文件 facebook_combined.txt，列出了所有 ego 网络的边
• readme-Ego.txt：提供上述文件的详细说明文档

在开始任何机器学习任务前，充分熟悉数据集结构至关重要。

1.2 使用 networkx 加载数据集

使用 networkx 加载聚合的 ego 网络，合并的 ego 网络以边列表形式呈现。我们可以通过 networkx 从边列表创建无向图：

G = nx.read_edgelist("facebook_combined.txt", create_using=nx.Graph(), nodetype=int)

打印关于图的基本信息：

print(f"Number of nodes: {G.number_of_nodes()}")
print(f"Number of edges: {G.number_of_edges()}")

输出如下所示，可以看到聚合网络包含 4039 个节点和 88234 条边，其边数达到节点数的 20 倍以上，表明这是一个连接高度密集的网络：

Number of nodes: 4039
Number of edges: 88234 

可视化网络将有助于更好地理解分析对象，使用 networkx 绘制图：

nx.draw_networkx(G, pos=spring_pos, with_labels=False, node_size=35)

输出结果如下所示：

可以观察到存在多个高度互联的枢纽节点。从社交网络分析视角来看，这些枢纽节点可能是潜在社交机制作用的结果，深入研究这些机制有助于理解个体社交关系网络的结构特征。
保存网络中自我用户的节点 ID。这些 ID 可从 facebook.tar.gz 压缩包内的文件中提取。首先，解压 facebook.tar.gz，解压后的文件夹名为 facebook，通过获取每个文件名的第一部分来检索 ID：

ego_nodes = set([int(name.split('.')[0]) for name in os.listdir("facebook/")])

在下一小节中，我们将通过检查图的属性来深入理解其结构特征，这将帮助我们更清晰地把握其拓扑结构和关键特性。

2. 网络拓扑和社区检测

理解网络拓扑结构及节点角色是社交网络分析的关键步骤。在社交网络中，节点实质上是具有独特兴趣、习惯和行为模式的真实用户。

2.1 网络拓扑

(1) 首先，计算同配性 (assortativity)，该指标能揭示用户是否倾向与连接度相似的节点建立连接：

assortativity = nx.degree_pearson_correlation_coefficient(G)

输出结果如下：

0.06357722918564912

可以看到，同配性为正值，这表明高度连接的用户倾向于相互关联，因为每个社交圈内部的用户通常存在密集连接。

(2) 传递性 (transitivity) 也有助于理解用户间的连接模式。该指标表示拥有共同好友的两人本身也是朋友的平均概率：

t = nx.transitivity(G)

输出结果如下所示：

0.5191742775433075

可以看到，概率大约为 50%，表示两个有共同好友的用户既可能建立也可能不存在朋友关系。可以通过计算平均聚类系数得到进一步验证——该系数可视为传递性的另一种定义形式：

aC = nx.average_clustering(G)

输出结果如下所示：

0.6055467186200876

需要注意的是，聚类系数通常高于传递性。这是因为根据定义，该指标更关注低连接度节点——由于这类节点的邻居对数量有限(即局部聚类系数公式中的分母较小)，其权重会被放大。

(3) 在明确整体拓扑结构后，我们可以进一步探究网络中每个个体的重要性。正节点重要性最基础的定义可通过中介中心性 (betweenness centrality) 来衡量——该指标统计经过某节点的最短路径数量，反映该节点在信息传播中的枢纽程度：

bC = nx.betweenness_centrality(G)
np.mean(list(bC.values()))

输出结果如下所示：

0.0006669573568730229

(4) 平均中介中心性较低，这与网络中大量非桥接节点的存在相符。但通过可视化增强处理，我们能更直观地观察关键节点。定义一个增强绘制函数来突显高中介中心性节点：

def draw_metric(G, dct, spring_pos):top = 10max_nodes =  sorted(dct.items(), key = lambda v: -v[1])[:top]max_keys = [key for key,_ in max_nodes]max_vals = [val*300 for _, val in max_nodes]plt.axis("off")nx.draw_networkx(G, pos=spring_pos, cmap='Blues', edge_color=default_edge_color,node_color=default_node_color, node_size=3,alpha=0.4, with_labels=False)nx.draw_networkx_nodes(G, pos=spring_pos, nodelist=max_keys, node_color=enhanced_edge_color,node_size=max_vals)

调用该函数进行绘制：

draw_metric(G, bC, spring_pos)

输出结果如下所示：

(5) 接下来，计算每个节点的度中心性，该指标与节点的直接连接数相关，能清晰反映节点的本地连接密度：

deg_C = nx.degree_centrality(G)
np.mean(list(deg_C.values()))
draw_metric(G,deg_C,spring_pos)

输出结果如下所示：

0.010819963503439287

度中心性可视化结果如下所示：

(6) 最后，结算接近中心性 (closeness centrality) 指标。该指标通过计算节点到网络中所有其他节点的最短路径平均长度，帮助我们理解节点间的信息传播效率：

clos_C = nx.closeness_centrality(G)
np.mean(list(clos_C.values()))
draw_metric(G,clos_C,spring_pos)

输出平均接近中心性：

0.2761677635668376

接近中心性可视化结果如下所示：

通过中心性分析可以发现，每个核心节点似乎都隶属于某个社区(因为这些核心节点可能对应网络中的自我中心节点)。尤其值得注意的是存在多个高度互连的节点群(从接近中心性分析中尤为明显)。因此，我们将在接下来的分析中重点识别这些社区结构。

2.2 社区检测

在社交网络分析中，最值得探索的图结构特征之一就是社区划分。以 Facebook 为例，用户的好友关系往往反映生活的不同维度：教育背景好友(中学、大学等)、每周足球活动的伙伴、聚会结识的朋友等。社交网络分析能够自动识别这类群体，既可以通过拓扑特性自动推断，也能结合先验知识进行半自动划分。
理想的社区划分标准是：最小化社区间连接(不同社区成员间的边)，同时最大化社区内连接(同一社区成员间的边)：

import communityparts = community.best_partition(G)
values = [parts.get(node) for node in G.nodes()]
n_sizes = [5]*len(G.nodes())
plt.axis("off")
nx.draw_networkx(G, pos=spring_pos, cmap=plt.get_cmap("Blues"),
edge_color=default_edge_color, node_color=values, node_size=n_sizes, with_labels=False)

输出结果如下所示：

在这个分析阶段，也可以探究自我用户 (ego user) 在已检测社区中的角色分布，增强这些特殊节点的显示效果：

for node in ego_nodes:print(node, "is in community number", parts.get(node))n_sizes = [5]*len(G.nodes())
for node in ego_nodes:n_sizes[node] = 250plt.axis("off")
nx.draw_networkx(G, pos=spring_pos, cmap=plt.get_cmap("Blues"), edge_color=default_edge_color, node_color=values, node_size=n_sizes, with_labels=False)# enhance color and size of the ego-nodes
nodes = nx.draw_networkx_nodes(G,spring_pos,ego_nodes,node_color=[parts.get(node) for node in ego_nodes])
nodes.set_edgecolor(enhanced_node_color)

输出结果如下所示：

可以看到，部分 ego 用户同属一个社区，这些用户在 Facebook 上可能存在真实好友关系，因此他们的自我网络存在部分重叠。通过对图结构的分析，可以发现网络中可识别出若干重要节点，同时这些节点所属的社群具有明显边界特征。