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

提出了一种基于带权图并行分解的层次化社区发现方法,该方法采用图划分的方式定义社区结构,并在这种社区结构之上实现了社会网络社区发现并行算法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用户浏览行为模型

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

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

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

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

针对传统的物化视图选择(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的最短通路长度,逐步比较,确定通路所过各边权值之和最小的即最短路径。在计算的过程中用矩阵记下最短路径所经过的所有结点,最后验证了其在无向和有向简单带权图中的有效性。

有向非负权图中经过必经节点集最短路径算法

传统的Dijkstra算法只是针对起点和终点求解最短路径,而不能解决从起点出发,经过必经节点集,到达终点的无重复节点且无回路的最短路径问题。为此,在有向非负权图中,提出了Dijkstra算法和回溯法相结合的方法。对Dijkstra算法改进,并求解关键节点(起点,终点和必经节点)间的最短路径,进而从关键节点所构成的矩阵中采用回溯法得到目标路径。通过实际的算法实现,测试大量的有向非负权图数据,证实了算法的有效性和正确性。

简单赋权图最短路问题的一种新解法

文中提出了一种解决赋权图最短路问题的新方法——层选法,它弥补了Dijkstra算法不能解决存在负权的最短路问题的缺陷,并且这种方法简单易行。

CLOUD法案隐含美国数据霸权图谋

2018年3月通过的美国《澄清域外合法使用数据法案》,即CLOUD法案,明确美国执法机构从网络运营商调取数据的权力具有域外效力,并附于相应的国际礼让原则,同时设置外国政府从美国调取数据的机制。这一法案赋予美国调取存储在国外数据的权力,更重要的是,将司法管辖权的依据由数据位置变为数据控制者的数据控制范围,实质上创建了一个关于数据主权划分标准的新框架,试图以此打破各国数据本地化政策的数据保护屏障,通过美国互联网产业优势牢牢把握全球数据资源的掌控权,并利用隐私保护和网络自由等融入美国价值理念,形成美国主导的数据主权规则体系。本文对这一法案所隐含美国数据战略和意图进行分析,并提出相应的应对建议。

处理负权图最短路及判定负环之Dijkstra算法的改进

最短路径搜索算法主要包括Floyd,Bellman-Ford及其优化SPFA,还有Dijkstra三种。本文简要分析了三种算法的框架及性能,根据发现的负权图处理问题,选择Dijkstra算法对处理负权图及判断负环给出进一步地说明与研究,讨论出新的算法并用实验验证了其正确性。

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

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

端方与“陶斋评权图”

看到这张老照片,我们会感受到一股浓重的历史气息扑面而来。经历过近一个世纪的风风雨雨,照片如此清晰并能保存到现在,可以说是十分难得的。这张老照片现保存在中国文物研究所,原为著名学者、金石学家陆和九藏《吉金图释拓本》的第二十一开图片,题为'陶斋评权图'。陶斋为端方号。

带权图最长路径的一种算法

定义图(邻接矩阵)类template【class T】class Graph{private:T*ver;//数组ver存贮图中各个顶点的数据int**edge;//数组edge为图的邻接矩阵int vers,edges;//变量vers和edges分别存贮图的顶点个数和边个数bool tag;//tag是个标记变量,若值为0表示是无向图。

3连通3正则权图圈权的一个猜想的证明

本文证实了Ｂｏｎｄｙ的猜想．证明了：设 Ｇ为简单 ３连通 ３正则权图，｜Ｖ（Ｇ）｜＝ｎ＞６，则Ｇ含圈Ｃ，使Ｗ（Ｃ）＞４Ｗ（Ｇ）／ｎ．

用人工智能技术解决有限权图中两点间最短路问题

本文对图论中有限权图最短路问题采用了人工智能技术中《图搜索过程》方法予以解决。目前国内公开出版的《离散数学》教材中对这一问题的常规解法均为迪克斯特拉算法,《图搜索过程》主要突出两点间最短路求法,比迪克斯特拉算法,在计算过程上要简便得多。

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

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