社会网络社团挖掘若干关键技术研究

发布时间：2018-04-25 07:21

本文选题：社会网络 + 社团挖掘　；参考：《国防科学技术大学》2012年博士论文

【摘要】：社会网络泛指由世界上具有复杂连接关系的、与研究目的相关的事物或对象所组成的一种网络，广义上的社会网络包括人际关系网络、酶蛋白质网络、生物链网络、新陈代谢网络以及以互联网为代表的各种社交网络等。社会网络可以抽象为一个具有复杂连接关系和结构的可演化图。通常，社团是一组内部连接紧密，外部连接稀疏的节点集合。社会网络社团挖掘对于加强对社会网络的拓扑结构理解、功能分析和行为预测具有重要的理论意义及实用价值，已被广泛应用于恐怖组织识别、新陈代谢路径预测、蛋白质相互作用网络分析、搜索引擎开发和网络舆情监控等诸多领域。本文针对社团挖掘的不同应用场景，分别就多重图模型下的社会网络、含有不完全连接信息的社会网络、二部图模型下的社会网络和多类型节点组成的社会网络的社团挖掘关键技术进行研究，主要贡献有： 1、提出了一种基于层次化子图树的多重图社会网络社团并行挖掘方法。根据多重图数学模型，社会网络中任意两个节点之间允许有多条连接边，每条边对应于一个连接属性，赋以一个自然数的权重。对于社会网络图中的任一子图，本文运用该数学模型，通过综合该子图各边权重之和与节点个数引入子图密度的概念，并基于从权重较低的边出发进行逐步分解的思想，构造了子图密度逐层递增的层次化子图树HAT，提出了一种针对静态社会网络的层次化社团并行分解更新算法。进而，根据动态社会网络在相邻时间段内的局部变化原理，提出了针对动态社会网络的层次化社团并行分解动态更新算法。模拟数据集上的实验表明，以上算法在社团挖掘的准确度上优于GN等同类算法；数千万边和节点规模的真实数据集上的实验表明，以上算法适于高度并行计算，可以有效应用于大数据社会网络的社团挖掘。 2、提出了基于节点亲近度和马氏距离的不完全信息社会网络社团挖掘方法。假设考察的社会网络各节点具有相同的属性，每个节点对应于一个n维属性值向量；节点之间的连接信息具有不完全性，即某些局部区域的某些连接未知。本文选取具有完全连接信息的某些区域作为学习的样本区域，首先引入节点亲近度的概念，任意一对节点的亲近度由各自连接的邻居数和公共邻居数的某个经验公式给出，亲近度越接近于1，节点对越亲近，为0的节点对视为不亲近。接着对样本区域的每个节点的n维值向量，乘以某个矩阵，将它们变换到一个称为马氏空间的新空间中，使越亲近的节点对，其值向量在马氏空间中的距离，即马氏距离越小。于是，问题便转化为能够迭代求解的数学规划问题：寻找马氏变换矩阵，使所有亲近的节点对，其马氏距离的亲近度之加权和达到最小，同时使不亲近的节点对的马氏距离之和达到最大。最后，通过以上学习过程得到的马氏矩阵，将整个社会网络中的所有节点变换到马氏空间中，经贪婪搜索，给出一种基于节点马氏距离的聚类算法，以及一种-近似社团启发式分解方法。经数千个节点规模的真实数据集的实验，表明本文提出的方法和解决方案是有效的。 3、提出了基于图像变换的二部图社会网络重叠社团挖掘方法。二部图社会网络指由两组子网组成的社会网络，边连接仅存在于不同子网的节点之间，子网内部没有任何边连接。其社团挖掘问题是要找出那些分属两个子网的两个社团，称为社团对，尽管社团内部各节点互不直接相连，却与共同的对方社团的节点有密切关联。设两组子网分别包含m个和n个节点，二部图连接关系可以用一个m×n的0/1关系矩阵或黑白图像描述。其社团对的挖掘问题转化为：如何通过整行(列)图像的不断交换与调整，使图像中的黑色像素点最大程度的聚合在一起。本文首先基于哈夫曼图像编码理论，，以信息量最小化为目标，改进了一种行(列)贪婪搜索与交换的双聚类迭代算法，使整幅图像分解成若干矩形块，找出那些黑像素点密度较高的块，也就挖掘出了相应的行社团和列社团。接着，进一步针对某些行(列)节点可能同时属于多个不同的行(列)社团的应用场景，提出了一种基于增益函数的重叠社团模式搜索双聚类算法，其核心思想是，对于某一其它行(列)社团的节点能否同时属于本社团，取决于该节点的加入能否使本行(列)社团得到正收益，为此引入增益函数，它是新老社团所对应的块状区域密度差异的加权和。模拟数据集和真实数据集上的实验表明，算法具有良好的二部图社团挖掘效果。 4、提出了一种具有多类型节点的社会网络社团挖掘方法。在多类型节点组成的社会网络中，连接既存在于同类节点之间，也存在于不同类节点之间，而社团组成仅限于同类节点。具有n类节点的社会网络的连接关系可以用n×(n+1)/2幅黑白图像描述。本文首先将第一类节点相关的n幅图像拼接成一长幅图像，与第二类节点相关的n-1幅剩余图像也拼成一长幅图像，以此类推。接着把社团挖掘问题转化为与二部图相似的长幅图像的行和列的交换问题，其差异主要在于列交换时必须注意保持各列的语义一致性，其复杂性主要表现在需要综合各长幅图像的黑像素点聚集度。本文运用哈夫曼图像编码理论，以最大化压缩描述上述所有图像为目标，分别在社团数量已知和未知条件下，提出了相应的多聚类贪婪搜索算法。模拟数据集和真实数据集上的实验表明，算法在聚类精度上优于NMF等同类算法。
[Abstract]:Social network refers to a kind of network composed of things or objects related to the purpose of research , such as interpersonal network , enzyme protein network , biological chain network , metabolic network and social networks represented by Internet .

In this paper , the key technologies of community mining of social network composed of the social network , the social network and the multi - type nodes under the multi - graph model are studied in this paper , which mainly contribute to the social network under the multi - graph model , the social network under the second graph model and the social network composed of the multi - type nodes .

1 . A multi - graph social network community parallel mining method based on hierarchical sub - graph tree is proposed . According to the multi - graph mathematical model , a plurality of connection edges are allowed between any two nodes in the social network .
Experiments on the real data sets of tens of millions of edges and nodes show that the above algorithm is suitable for highly parallel computing and can be used for community mining of large data social networks .

2 . An incomplete information social network association mining method based on node affinity and Markov distance is proposed . It is assumed that each node of the social network has the same attribute , and each node corresponds to an n - dimensional attribute value vector ;
In this paper , we choose some areas with complete connection information as the sample area of learning , first introduce the concept of node affinity , and then transform them into a new space called Markov model .

This paper proposes a two - cluster iterative algorithm based on image transformation , which is composed of two groups of sub - networks .

4 . A social network association mining method with many types of nodes is proposed . In a social network composed of many types of nodes , the connection exists between the same kind of nodes , but also exists between different nodes , and the association of the association can be described by n 脳 ( n + 1 ) / 2 black and white images .

【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP393.09

【参考文献】