Web网络社区发现中若干关键问题研究

摘要

随着Internet和通信技术的迅猛发展，Web网络开始逐步渗透到人类生活和生产的各个方面，在人们的信息交流、工作生活等方面都发挥着极为重要的作用。数以亿计的用户在各种Web网络平台上不断地进行信息交互，使得网络数据日益庞大和复杂化，从而给Web网络社区发现研究提出了新的问题和挑战：(1)面对大规模的网络数据，如何利用有限的局部信息实现快速准确的局部社区发现？(2)在Web网络节点多模化，网络关系多维化的背景下，如何基于异质网络发展出准确有效的社区发现方法？
　　面对Web网络的局部性与异质性，传统的社区发现方法往往难以适用，无法有效地揭示局部或异质网络环境下的社区结构特征。围绕着Web网络社区发现的这两个关键问题，论文基于现有问题研究适用于局部网络和异质网络的社区发现方法。主要的研究工作如下：
　　1.针对局部社区边界节点难以确定的问题，提出了一种基于边界识别的局部社区发现算法。该方法一方面通过全面分析局部社区邻接子图范围内连接相似性，从而获取给定节点所在社区的局部结构特征并进行节点聚类；同时在社区聚类过程中，基于邻接节点内外的连接状况反复识别其边界节点，从而控制社区聚类的规模和范围以完成局部社区发现。该算法采用了有别于最大化局部社区结构指标的思路和方法，以节点相似性模块度作为局部社区发现的衡量标准，通过边界节点识别解决已有方法存在的“何时停止聚类迭代”和给定节点位置敏感等问题。
　　2.针对给定节点位置不确定性对局部社区发现的影响，提出了一种基于核心节点跳转的局部社区发现算法，该方法避免从给定节点直接扩张，而是搜索给定节点附近的核心节点，由邻近核心节点扩展为核心节点子团；并建立基于节点子团的适应度函数，据此进行节点子团合并以实现局部社区发现。与传统的基于给定节点的局部社区相比，该方法能从任意给定节点跳转到核心节点，从而能够有效避免给定节点自身的位置和影响力对社区发现的限制和影响；同时，该方法能够较为精确地控制局部社区的聚类过程和节点归属，并确定社区范围内的核心节点分布。
　　3.为将二分网络、多模网络和多维网络统一在同一框架下，提出了异质网络模型。受二部图模型启发，该模型将异质网络描述为多个关联的二部图结构。该异质网络模型既能准确地描述异质网络数据本身，也能反映异质节点之间的复杂关系。更重要的是，该模型使得最简单的异质网络——二分网络与多模/多维网络在模型概念上得到了有效地统一和兼容，为后续的异质网络结构挖掘提供了的理论基础，使得引入更多方法来解决异质网络社区发现的问题成为可能。
　　4.为避免二分网络二分结构对社区发现的限制，提出了一种基于图正则化的三重非负矩阵分解（F-NMTF）算法。通过分别构建两类异质节点的近邻图来估计用户子空间和目标子空间的结构特征，将其作为正则化约束项引入到NMTF模型中，从而同时引入了类间信息和类内信息，以增强非负矩阵分解的正交性和收敛性，并摆脱二分结构的限制；同时将NMTF分解为两个关于交替求解最小化函数的子问题，并给出了一种乘性更新因子矩阵的交替迭代算法，从而使矩阵分解迭代得以简化，加快收敛速度。实验和分析证明：对于计算机生成网络和真实网络，F-NMTF的社区划分方案均表现出有较高的准确率和稳定性，能够准确有效地挖掘二分网络的社区结构。
　　5.为充分有效地挖掘异质网络中复杂的多模或多维关系，提出了一种基于多视图学习的联合矩阵非负分解算法(Joint-NMF)。基于异质网络模型，该方法将异质网络数据转化为多个相关联的二部图；借鉴多视图（Multi-view）的分析方法，将基于单个图的半监督学习扩展到多个视图的情况，使不同的二部图之间能够提供互信息，以实现异质网络图间的协同学习。Joint-NMF算法在整个聚类学习过程综合考虑了异质网络图的网络结构，从而使得所有二部图学习器对中心模式节点的划分趋于一致。实验结果表明：在异质网络条件下，综合多个二部图结构的半监督算法Joint-NMF比无监督算法有更优的社区发现性能。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 Web网络社区发现的背景与意义

1.2 社区发现研究的相关工作

1.3 Web网络社区发现中若干关键问题

1.4 论文主要工作和章节安排

第二章 Web网络社区发现的关键问题概述

2.1 社区发现的基本概念

2.2 Web网络模型与社区结构特征

2.3 基于局部性和异质性的社区发现研究现状

2.4 小结

第三章 基于边界识别的局部社区发现

3.1 引言

3.2 局部社区发现的研究现状

3.3 基于边界识别的局部社区发现

3.4 实验与结果分析

3.5 小结

第四章 基于核心节点跳转的局部社区发现

4.1 引言

4.2 基于核心节点跳转

4.3 基于核心节点跳转的局部社区发现

4.4 实验与结果分析

4.5 小结

第五章 基于图正则化的二分网络社区发现

5.1 引言

5.2 问题分析

5.3 半监督学习

5.4 非负矩阵分解在社区发现的应用

5.5 基于图正则化的二分网络社区发现

5.6 实验与结果分析

5.7 小结

第六章 基于多视图学习的异质网络社区发现

6.1 引言

6.2 问题分析

6.3 多视图学习在异质网络社区发现的应用

6.4 基于多视图学习的异质网络社区发现

6.5 实验与分析

6.6 小结

第七章 结束语

7.1 论文主要创新点与研究成果

7.2 后续工作展望

致谢

参考文献

作者简历 攻读博士学位期间完成的主要工作