加权社会网络中重要节点发现算法

从社会网络中发现重要节点是一个很有意义的研究问题,目前多数重要节点发现方法是基于不加权网络。由于在社会网络中,节点之间的关系具有强弱差异,社会网络本质上是一个加权网络。对于加权社会网络中的重要节点发现较少有研究。利用节点交互,提出了节点间关系强度的一种度量方法,该方法考虑了节点局部有向交互特征与全局交互特征。利用节点的行为特征定义了节点活跃度。 采用关系强度作为边的权重,活跃度作为节点权重形成了加权社会网络。基于PageRank算法的思想,提出了两个改进算法,算法采用节点权值作为阻尼系数,在迭代式过程用边的权重代替了PageRank算法中的入边和。分别选择国内外具有代表性的2个社交网络上的数据集进行大量实验,并分别选择了不同的方法作为比较,实验结果表明改进算法能较好地发现加权社会网络中的重要节点。     

加权社交网络敏感边的差分隐私保护研究

社交网络边权重表示节点属性相似性时,针对边权重能导致节点敏感属性泄露的问题,提出一种利用差分隐私保护模型的扰动策略进行边权重保护。首先根据社交网络构建属性相似图和非属性相似图,同时建立差分隐私保护算法;然后对属性相似图及非属性相似图边权重进行扰动时,设计扰动方案,并按扰动方案对属性相似图及非属性相似图进行扰动。实现了攻击者无法根据扰动后边权重判断节点属性相似性,从而防止节点敏感属性泄漏,而且该方法能够抵御攻击者拥有最大背景知识的攻击。从理论上证明了算法的可行性,并通过实验验证了算法的可行性及有效性。     

基于节点加权和边加权的重分形研究

目前对于网络重分形的研究,在网络权重性质方面主要是原始网络、节点加权网络、边加权网络,每一个都是单独进行研究,论文主要对同时包含节点权重和边权重的网络进行分析,研究网络广义分形维数的变化情况。首先对已有的沙箱算法进行改进,并利用分形布朗运动时间序列进行改进算法的验证,然后利用改进的沙箱算法对由分形布朗运动时间序列生成的同时包含节点权重和边权重的可视复杂网络进行计算,接着同时单独改变边权重和节点权重,进一步研究广义分形维数随边权重和节点权重改变的变化情况。结果表明改进沙箱算法在保持了传统沙箱算法计算精度的前提下,大大地提高了计算的速度。对于同时单独改变节点权重和边权重,对复杂网络的广义分形维数的影响是截然不同的,节点权重的变化基本不影响网络广义分形维数的变化,而边权重则大大的影响且不同权重指数下的影响情况各不相同。     

针对社交网络边权重的差分隐私保护

针对社交网络边权重隐私保护中的弱保护和最短路径不可分析问题,提出一种满足差分隐私保护模型的边权重保护策略。将社交网络划分为全次图、缺次图、零次图,设计扰动方案及查询函数,对不同图进行查询获取其边权重并按扰动方案对不同的边权重添加不同的Laplace噪声,实现抵御攻击者拥有最大背景知识的攻击的边权重隐私保护,保证一组节点的最短路径不变,且其长度与原路径长度相近。该策略有强保护性及最短路径可分析性,从理论上验证了算法的可行性,通过实验验证了算法的正确性。     

基于联邦学习的SDN异常流量协同检测技术

网络流量异常状态检测是发现潜在安全威胁的重要手段，但是现有异常流量检测方法普遍存在环境适应性不强、协同能力较弱等问题。结合SDN网络的拓扑结构与流量特征，提出基于联邦学习的异常流量协同检测技术。利用SDN网络中的检测节点，构建基于联邦学习的多检测节点协同检测架构。通过信息熵计算提取流量特征，从相对熵的角度分析检测节点的流量关联度，并根据该关联度设计模型训练过程中的参数聚合权重优化算法，提高检测模型的适应能力。应用参数聚合权重优化算法进行多检测节点异常流量检测模型的协同训练，提升检测模型对异常流量的识别准确率。仿真结果表明，与本地独立训练和传统联邦学习算法相比，基于参数聚合权重优化算法的识别准确率分别提升了31.69%和7.92%，具有更好的异常流量检测效果及更强的环境适应能力。     

基于图神经网络的动态网络异常检测算法

动态变化的图数据在现实应用中广泛存在,有效地对动态网络异常数据进行挖掘,具有重要的科学价值和实践意义.大多数传统的动态网络异常检测算法主要关注于网络结构的异常,而忽视了节点和边的属性以及网络变化的作用.提出一种基于图神经网络的异常检测算法,将图结构、属性以及动态变化的信息引入模型中,来学习进行异常检测的表示向量.具体地,改进图上无监督的图神经网络框架DGI,提出一种面向动态网络无监督表示学习算法Dynamic-DGI.该方法能够同时提取网络本身的异常特性以及网络变化的异常特性,用于表示向量的学习.实验结果表明,使用该算法学得的网络表示向量进行异常检测,得到的结果优于最新的子图异常检测算法SpotLight,并且显著优于传统的网络表示学习算法.除了能够提升异常检测的准确度,该算法也能够挖掘网络中存在的有实际意义的异常.     

基于隐马尔可夫随机场的社区结构发现算法

针对社区结构发现问题,提出了一种基于隐马尔可夫随机场社区发现算法.该方法将网络中的顶点度数映射为顶点信息值,用马尔可夫随机场模型描述网络中上下文信息并构造系统能量函数,使用迭代条件模式算法对能量方程进行优化.该方法在Zachary空手道俱乐部网络、海豚关系网络以及美国大学足球联赛网络上进行验证,实验结果表明,该算法的准确率较高.     

社交网络中个体价值分析

社交网络中个体价值分析,就是利用网络爬虫抓取社交网络中数据,对数据过滤分析,抽象成图结构,发现排名最高的节点(个体)。本文基于Page Rank算法模型,应用"黄金分割线"方法和"二八定律"对其进行改进,并用在社交网络中,定义以人为核心的个体价值,这样Page Rank模型就有了新的应用领域,同时也有了一个新的名字"People Rank"。本文将复杂的社交网络抽象成一种图结构,图中节点代表用户,图中边的链入链出代表了用户之间的"粉丝"和"关注"关系。利用"People Rank"模型,构建矩阵,对矩阵进行迭代计算,最后得到一个收敛的结果,根据结果的大小确定在社交网络中个体的重要性。     

变权重MRF算法在图像自动无监督分割中的应用

为了实现图像的自动无监督分割,本文提出类自适应变权重马尔可夫随机场分割算法。首先结合最小描述长度准则,自适应计算马尔可夫随机场框架下的图像分类数;然后引入变权重的马尔可夫随机场算法,扩大势函数的选择范围,消除势函数的复杂计算;最后用迭代条件模式进行优化,获得最大后验概率准则下的分割图像。在Matlab环境中的测试结果表明,该算法具有实效性,能正确计算分类数,同时有效减少了分割错误。     

基于异质图卷积注意网络的社交媒体账号分类

由于社交媒体网络的复杂性, 单一性质的同质信息网络对社交媒体账号分类会造成信息丢失, 对分类结果产生不利影响. 针对这种问题, 本文提出基于异质图卷积注意网络的社交媒体账号分类方法(HGCANA). 首先构建社交媒体的异质信息网络, 然后提取异质信息网络的社交媒体特征, 引入注意力机制, 对社交媒体账号进行分类识别. 通过实验比较HGCANA方法与现有方法, 证明了本文提出的HGCANA方法能够更好地对社交网络媒体账号进行有效分类.     

Stochastic graph as a model for social networks

Social networks are usually modeled and represented as deterministic graphs with a set of nodes as users and edges as connection between users of networks. Due to the uncertain and dynamic nature of user behavior and human activities in social networks, their structural and behavioral parameters are time varying parameters and for this reason using deterministic graphs for modeling and analysis of behavior of users may not be appropriate. In this paper, we propose that stochastic graphs, in which weights associated with edges are random variables, may be a better candidate as a graph model for social network analysis. Thus, we first propose generalization of some network measures for stochastic graphs and then propose six learning automata based algorithms for calculating these measures under the situation that the probability distribution functions of the edge weights of the graph are unknown. Simulations on different synthetic stochastic graphs for calculating the network measures using the proposed algorithms show that in order to obtain good estimates for the network measures, the required number of samples taken from edges of the graph is significantly lower than that of standard sampling method aims to analysis of human behavior in online social networks.     

WSM: a novel algorithm for subgraph matching in large weighted graphs

Given an undirected/directed large weighted data graph and a similar smaller weighted pattern graph, the problem of weighted subgraph matching is to find a mapping of the nodes in the pattern graph to a subset of nodes in the data graph such that the sum of edge weight differences is minimum. Biological interaction networks such as protein-protein interaction networks and molecular pathways are often modeled as weighted graphs in order to account for the high false positive rate occurring intrinsically during the detection process of the interactions. Nonetheless, complex biological problems such as disease gene prioritization and conserved phylogenetic tree construction largely depend on the similarity calculation among the networks. Although several existing methods provide efficient methods for graph and subgraph similarity measurement, they produce nonintuitive results due to the underlying unweighted graph model assumption. Moreover, very few algorithms exist for weighted graph matching that are applicable with the restriction that the data and pattern graph sizes are equal. In this paper, we introduce a novel algorithm for weighted subgraph matching which can effectively be applied to directed/undirected weighted subgraph matching. Experimental results demonstrate the superiority and relative scalability of the algorithm over available state of the art methods.     

一种HRG模型初始化算法及在链路预测中的应用

在利用层次随机图（HRG）模型对真实网络进行链路预测的过程中,需要构造一个初始层次随机图来初始化马尔科夫链以运行马尔科夫链蒙特卡洛抽样算法。针对现有的层次随机图初始化方案效率不高的问题,本文对初始层次随机图模型进行重建,提出一种新的层次随机图模型初始化算法。该算法分为2个阶段,第一阶段引入相似性指标（LHN-I指标）为网络中的边进行排序;第二阶段利用排序好的边对层次随机图模型进行构造。在该过程中,设计一种将网络顶点插入到层次随机图模型中的方法。通过3个实例网络对提出的算法与现有算法的性能进行比较,实验结果表明,利用提出的初始化算法构造出的初始层次随机图不仅有着较高的似然值,而且使得马尔科夫链蒙特卡洛算法能够更快地收敛,进而降低链路预测的时间消耗。除此之外,在链路预测实验中,改进的基于层次随机图模型的链路预测算法相比一些基于相似性指标的链路预测算法有着较好的预测精度。     

改进的k度匿名图构造算法

在社交网络中, 为防范用户隐私泄漏, 在用户数据发布前需要做匿名化处理. 针对以节点度数为背景知识的隐私攻击, 将社交网络匿名化问题建模为图的k度匿名化问题; 其主要方法是对图添加尽可能少的边或点来满足度匿名化要求, 其中要求添加边或点较少是期望尽可能保持原图结构特性. 目前, 加边类算法并不能很好地保留平均路径长度等结构特性; 加边且可加点类算法尽管能更好地保留原图结构特性, 但添加的边或点较多. 本文融合两类算法的策略提出改进算法. 新算法利用贪心法生成匿名度序列, 然后基于社区结构加边, 并且优先满足其匿名代价高于平均匿名代价的节点的匿名化要求; 若加边不能完成匿名化, 则通过加点实现图匿名化. 真实数据集上的实验结果表明新算法能更好地保留图的几种典型的结构特性, 并且添加的边或点更少.     

Clustering large attributed information networks: an efficient incremental computing approach

In recent years, many information networks have become available for analysis, including social networks, road networks, sensor networks, biological networks, etc. Graph clustering has shown its effectiveness in analyzing and visualizing large networks. The goal of graph clustering is to partition vertices in a large graph into clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structures, but largely ignore the vertex properties which are often heterogeneous. Recently, a new graph clustering algorithm, SA-cluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SA-Cluster performs matrix multiplication to calculate the random walk distances between graph vertices. As part of the clustering refinement, the graph edge weights are iteratively adjusted to balance the relative importance between structural and attribute similarities. As a consequence, matrix multiplication is repeated in each iteration of the clustering process to recalculate the random walk distances which are affected by the edge weight update. In order to improve the efficiency and scalability of SA-cluster, in this paper, we propose an efficient algorithm In-Cluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost Inc-Cluster can save. We further design parallel matrix computation techniques on a multicore architecture. Experimental results demonstrate that Inc-Cluster achieves significant speedup over SA-Cluster on large graphs, while achieving exactly the same clustering quality in terms of intra-cluster structural cohesiveness and attribute value homogeneity.     

基于谱约束和敏感区划分的社会网络隐私保护扰动方法

针对社会网络中以社会个体邻域信息作为背景知识进行敏感边识别的攻击,提出了基于谱约束的敏感区划分随机扰动方法。该方法的主要思想是将网络分为敏感区和非敏感区,根据前一次扰动后社会网络图与原始社会网络图谱大小的关系,再基于谱约束条件选择合适的边对社会网络图随机地增删或转换扰动,从而提高社会网络数据的可用性。该方法可以排除无效扰动以提高隐私保护程度,实验结果表明在隐私保护的同时可更好地保持社会网络的结构特性。     

基于节点分割的权重序列隐私保护研究

针对加权社会网络的数据发布和权重序列攻击,提出采用基于节点分割的权重序列匿名方法实现网络结构、边权重以及权重序列的隐私保护。此方法在图的边空间概念的基础上,采用节点聚类分割思想构建加权社会网络的向量集模型,利用边的介数中心性重新分配权重,通过组内直径距离和节点的相对距离调整权重序列,利用加权欧式距离构建候选向量集,从候选向量集中选取向量实现社会网络的数据发布。此方法在保证隐私安全的前提下,保证了社会网络分析需要的结构特征、发布数据的有效性以及有效地抵御了权重序列攻击。     

基于层次随机图模型的脑网络链路预测

针对一般链路预测算法在具有层次结构的脑网络中计算效率低且复杂度高的问题,提出了一种基于最大似然估计的层次随机图模型。该算法首先利用脑网络数据建立层次随机图,然后通过改进的马尔科夫蒙特卡罗算法采样树状图空间,最后计算脑网络边的平均连接概率,且通过评价指标对算法进行评价。实验结果表明,利用该算法对脑网络和3种不同的层次结构网络进行链路预测比较, 脑网络的预测结果最好。此外,所提出的算法较之传统的基于相似性的算法,该算法效果明显,且具有理想的计算复杂度。     

基于FP-Growth的图上随机游走推荐方法

推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。