社交网站的大量涌现,针对社交网络的隐私保护成为研究焦点之一。数据有用性与隐私保护程度之间的平衡,仍然是当前隐私保护方法研究所要面对的一个基本问题。目前常用的隐私保护方法包括匿名化技术、泛化技术、随机扰动技术等。匿名化技术复杂但数据可用性尚可,后两者技术相对简单但数据可用率低。最小生成树聚类方法是基于图论的一种典型聚类方法,算法简洁,利用了最小生成树的最佳子结构特点即本质上是最小权重生成树,同时可保留网络的某些重要特性如最短路径不变。兼顾数据的可用性与隐私保护程度,基于最小生成树（MST）聚类技术与泛化技术,本论文提出一种面向带权社交网络的子图泛化隐私保护方法,所做的主要工作如下:（1）针对带权社交网络提出了基于MST（最小生成树）聚类的子图泛化隐私保护方法。对于带权社交网络,首先将其去掉环边,转换为最小权值生成树连通图,网络的某些重要特性如最短路径不变;然后在计算并判断最小生成树的所谓“不一致边”的基础上,进行最小生成树MST聚类,聚类将最小生成树分成多个子图（聚类）;（2）提出了带权社交网络子图的三种泛化模式:泛化技术通过对网络的相关不同属性泛化为相同的属性值或某个范围的区间值来实现属性匿名、隐藏细节,以达到提高数据的隐私保护性。因此在MST聚类的基础上,按三种模式进行子图泛化,即平均边权值子图泛化模式、最小边权值子图泛化模式、最大边权值子图泛化模式。同时对于MST所谓的“不一致边”即各个子图（聚类）的分界边,边权值保持不变即该类边的泛化值为原值;对生成MST过程中去掉的环边,若该边的两端点同处于同一子图（聚类）,则按以上三种模式进行泛化,若此类边的两端点处在不同子图（聚类）中,该边的权值不变即泛化值不变;（3）实验验证了提出方法的有效性:通过实验分析验证本文提出的基于MST聚类的带权子图泛化的社交网络隐私保护算法（MST-SGG）的有效性。选取了Pattern Recognition Example数据集以及Pajek测试集（“test networks”）中若干数据集（即SHR.net,Write.net,GR3₅3.net）为基础,构建了带权无向网络测试集,并使用网络边权值序列损失率作为子图泛化后的数值评价指标。另外提出的隐私保护方法,不改变网络的拓扑结构即在子图泛化提高隐私保护的同时,尽量保留泛化后的子图边界不变以提高数据的有用性,故对于网络节点度没有影响,同时加权网络的最短路径等特性取决于边值序列分布,当边序列损失率较小时,此类特性值的变化也会很小。结论:要提高网络的隐私保护性,一般来说,必然会导致数据的可用性下降,因此要兼顾两者,达到某种平衡。由于提出的MST-SGG泛化算法,对于不同聚类（子图）的边界（即不同聚类（子图）间的所谓“不一致性边”等）没有泛化,使得泛化后的不同聚类（子图）的边界得以保留,因而对于诸如数据挖掘而言,泛化后的聚类结果基本不受影响,提高了数据的可用性。由实验结果及其分析可知,本文提出隐私保护算法有效、可行,即对于不同规模的带权网络,可选择适中的MST-聚类数目子图进行泛化,既可以降低网络边权值序列损失率而达到提高网络数据的可用性,也借由子图泛化而对网络提供一定的隐私保护性。