基于带权图的层次化社区并行计算方法

提出了一种基于带权图并行分解的层次化社区发现方法,该方法采用图划分的方式定义社区结构,并在这种社区结构之上实现了社会网络社区发现并行算法P-SNCD(parallel social network community discovery).P-SNCD算法有效地避免了传统的基于"模块度"的社区发现方法倾向于发现相似规模社区的弊端.同时,该算法能够以可扩展的方式,在处理器规模为O(hmn)或O(hn2)的条件下,以并行计算时间复杂度为O(logn)高效地挖掘大规模复杂社会网络中社区密度为h的社区,其中,n为社会网络节点数,m为边数,h为用户指定的任意社区密度.所提出的算法对用户参数输入要求简单,从而使得算法具有较强的实用性.充分的实验数据验证了所提出算法的精确性和高效性.

带权图的均衡k划分

带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集S的顶点权值之和满足要求.此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明,当k分别取值为2,4,8时所提算法分别在86%,81%,68%的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60%以上.

带权图的多重分形研究

自相似特性是复杂网络研究的重点,分形维数是度量其自相似特性的重要工具.针对带权图中节点权重与边权重可以为正实数、负实数、纯虚数及复数等多种不同数值的情形,给出各种不同带权图的多重分形维数,讨论了带权图的多重分形特性.研究表明,在不同类型的带权图中,除节点权重及边权重均为正实数的情形之外,其他类型的带权图均具有多重分形特性.最后分析了这些带权图多重分形维数的性质.

基于有向带权图的页面聚类算法研究

聚类算法是数据挖掘中的一个重要的分析工具。Web使用挖掘中的聚类分析一般分为用户聚类和页面聚类。其中页面聚类是指导网站结构离线优化的重要方法。利用有向带权图表示用户的访问会话记录,对建立的有向带权图模型运用聚类算法实现页面聚类。选取真实数据对典型的聚类算法K-means算法、DBSCAN算法和COBWEB算法进行实验。实验结果表明,在选取的数据集范围内,COBWEB算法准确率要高于K-means算法和DBSCAN算法,时间性能与用户访问频率矩阵大小有密切关系。

基于有向带权图的Web用户浏览行为模型

建立反映用户浏览特征的Web用户浏览行为模型是Web挖掘的关键。本文通过有向带权图来描述用户浏览行为,首先通过数据集构造出了Web站点的拓扑结构,再引入Markov链模型来描述团体成员的网页访问活动,对用户浏览行为进行分析,并对链接的权值进行了计算,最后综合利用构造出的Web站点的拓扑结构和Markov链转移概率矩阵描述的用户浏览特征得到了描述用户浏览行为的有向带权图模型。

基于带权图的多维大数据模型优化算法

针对传统的物化视图选择(materialized view selection,MVS)算法评价指标单一(仅评价物化时间,过度追求物化视图的查询命中率)会导致超高维度时的维度灾难以及物化视图集频繁抖动的问题,本文提出了一种基于带权图的多维大数据模型优化算法(multi-dimensional big data model optimization,MMO),通过引入平均查询时延和膨胀率评价指标,基于带权图模型找出物化视图集的最优解。实验结果表明,本文算法在综合评分、平均查询时延、膨胀率方面均优于粒子群算法(particle swarm optimization,PSO),解决了超高维数据下的维度灾难问题,并且能够快速收敛。

带权图Laplacian矩阵次小特征根下界

谱图理论是图论的重要研究分支,其思想广泛应用于计算机科学的各个领域.带权图Lap lac ian矩阵的次小特征根λn-1的估计被应用于在图像分割和图数据表示中.用代数方法对λn-1的下界进行估计,并讨论非带权图情况下λn-1的下界.

带权图的多重分形度量

分形维数及多重分形是分形理论的重要研究内容。复杂网络的多重分形已经得到了较为深入的研究,但对复杂网络多重分形的度量目前并没有可行的方法。带权图是复杂网络研究的重要对象,其中的节点权重及边权重可以为正实数、负实数、纯虚数及复数等多种不同的类型。除节点权重及边权重均为正实数的情形外,其他类型的带权图都具有多重分形特性,且均具有无穷多个复数形式的网络维数。通过对带权图多重分形的研究,文中给出了15种具有多重分形特性的带权图多重分形维数的模所构成的集合,并采用集合的势对带权图的多重分形特性进行度量。研究表明,15种带权图多重分形维数的模所构成的集合均是可数集,其中有2种集合是2重集合,另外13种集合是通常意义上的集合,而且所有的集合均是等势的,其势均为■0。

邻接矩阵求带权图中最短通路

通过对带权邻接矩阵定义一种运算,计算n阶简单带权图中任意两点之间步长为1,2,…,n-1的最短通路长度,逐步比较,确定通路所过各边权值之和最小的即最短路径。在计算的过程中用矩阵记下最短路径所经过的所有结点,最后验证了其在无向和有向简单带权图中的有效性。

带权图最短路径的基于邻接表的快速算法

本文首先阐明了带权有向图求最短路径问题的含义,并认为无向图是一种有向图的特例,然后针对一般的带权有向图,给出了一种用邻接表作为存储结构时求源点到任一顶点最短路径的算法。

权长相合的带权无向图画图算法

针对带权无向图的输出需用边长反映权值大小的问题,提出了一种基于遗传算法的带权无向图画图算法,通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标,变异算子结合了非一致性变异和单点邻域变异,并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明,该算法画出的图形连线无交叉,分支清晰,权值—长度相合,能得到清晰、美观且能直观反映权值的可视化输出结果,可应用于带权无向图的可视化输出系统的设计。

一种基于三维曲面变形的自由变形算法

在Dirichlet自由变形算法的基础上,针对Dirichlet自由变形方法不适合三维曲面变形的情况,提出了一种基于曲面两点之间最短距离的Dirichlet自由变形算法:算法将三维曲面上求两点之间最短距离问题转化为二维平面上求带权图最短路径问题,用三角面片的面积之和来表示Voronoi单元或部分Voronoi单元面积,并由此给出了一种适合由多边形表示的三维曲面的Voronoi图构造方法及Sibson邻居和Sibson坐标的计算方法;并且用该算法对人脸模型进行局部变换,进一步刻画特定人脸器官的细节特征,最终形成了个性化的三维人脸模型.

改进的Graphcut算法

分析了查找路径时高权值边的存在对于合成结果的影响,在graphcut算法的基础上,针对其在查找最优路径时,没有考虑到高权值的边对于路径选取的影响这一缺点,结合其将重叠区域看作一个带权图的优点,对其进行了改进,提出了一种新的查找最优路径的算法,采用一种新的度量距离的方法,对算法查找到的最短路径进行选取,得出最优路径,避免了路径上高权值边的存在,使人眼不易察觉块间接缝的不连续,提高了合成质量。

最短路径问题的若干算法的编程

本文讨论了带权图的最短路径问题的三类不同情况，针对每种情况介绍了较好的算法，并在MATLAB软件环境下编制了这些算法的程序。通过一个实例，验证了算法的正确性。

基于Floyd算法建模的研究应用

对带权图中所有顶点之间的最短路问题,通常采用Floyd算法.详细阐述了Floyd算法的基本思想、求解步骤及一种简便的路径标记方法。通过实例讨论了Floyd算法在实际生产生活如选址问题、高速公路收费系统中的应用。

降维理论中特征值的估计

利用谱降维方法可以归结为求解带权图Laplacican矩阵L(G)的特征值λn-t对应的特征向量这一理论,通过代数方法估计λn-t的下界,并讨论非带权图的情况下λn-t的下界.

最小生成树与构造造价最低通讯网

如何构造造价最低的通讯网络，是信息社会面临的共同问题，本文从普里姆（prim)求解最小生成树的基本思想入手，给出了让计算机自动构造耗费最低的通讯网的方法。

复杂网络的节点重要性研究

介绍了一种带权图来表示节点间关系的强弱,图可以直接反映一个节点互联互动频率,通过权重的计算,它可以测量当地的重要性节点结果表明,当地的重要性节点节点的程度是成正比的,节点的互动频率.在某些情况下,当地重要的是其相邻节点的程度成反比.

一种基于TextRank的单文本关键字提取算法

作为一种经典的文本关键字提取和摘要自动生成算法,TextRank将文本看做若干单词组成的集合,并通过对单词节点图的节点权值进行迭代计算,挖掘单词之间的潜在语义关系。在TextRank节点图模型的基础上,将马尔可夫状态转移模型与节点图相结合,提出节点间边权为条件概率的新模型生成算法TextRank_Revised。通过对有标记和无标记的验证集进行验证,证明新的算法在不提升时间复杂度的前提下,通过计算单文本得出的单词排序结果相较于原TextRank算法更加吻合人工对文档的关键字提取结果。

最短路径及其变形问题的算法

讨论了一个带权图的最短路径的算法及其若干个变形问题的算法,并在MATLAB软件环境下对最短路径问题给出了一个简捷易懂的程序。这些算法在实际应用中有较强的实用性。