一种对分划分的复杂网络社团检测方法

在许多领域,例如社会科学,技术科学及生物科学,复杂网络中的社团发现是一项重要任务。这些社团结构暗含着系统功能方面的信息并用来帮助人们理解网络的功能及增长机制。谱分优化了由李等人最近提出的一种用来评估和发现社团的模块密度函数。提出了一种对分算法,该算法使用模块密度矩阵的主特征向量迭代来检测网络社团结构。在一个经典的计算机产生的随机网络中检验了算法。当社团结构变地模糊时,实验结果显示这种新的算法在发现复杂网络社团上是有效的。     

关于超网络的一点思考

在探讨超网络的内涵时提到,除了Nagurney所着重研究的多层超网络之外,还有一类基于超图(hypergragh)的超网络(hypernetwork)值得关注.超图的特点是图中的边可以连接两个以上的节点,这对研究信息与知识网络的研究与应用会有独特的用途.以知识的超网络表述为例,介绍了基于超图的超网络的简单应用.     

一种基于混合超图的R~2空间知识表示模型

现有的基于一般图论的空间知识表示模型难以反映知识系统的复杂构成和所隐含的组织结构。针对这一问题,引入混合超图(Hybrid hypergraph)的思想,提出一种基于混合超图的空间知识表示模型,用来组织规模巨大、连接复杂多样且具有嵌套特性的空间知识网络。该模型用混合超图的超边来表示多元空间关系。对基本的二元区域拓扑关系进行扩展,提出了多元的超拓扑关系来定性地描述多个空间对象间的分离、相连和包含等。以超拓扑关系为例,通过对一个小型环境的表述,说明了基于混合超图的空间知识表示模型的应用,为复杂空间知识的表示、组织和分析提供了一种新的工具和思路。     

采用离散粒子群算法的复杂网络重叠社团检测

针对复杂网络重叠社团检测的问题,建立了衡量重叠社团划分优劣的评判函数,并基于该函数提出了一种采用混沌量子粒子群优化的复杂网络重叠社团检测算法。该算法采用量子编码,利用Logistic映射初始化粒子种群,并以粒子群速度改变方式更新转角的大小,以概率为1收敛。实验结果表明,所提算法具有较高的检测正确率,能更好地反映实际社团划分情况。     

四元超图的模型及其性质

提出了一种基于复杂网络理论的四元超图的模型。定义了基本的网络衡量值,研究了四元超图中顶点的度分布及额外度的分布,构建了随机四元超图的模型,并且探讨了巨大分支在四元超图中存在的条件。本研究可用于分析研究社会网络中一些大规模的复杂超网络的结构及其拓扑性质。     

基于超图的社交网络中的预算影响力最大化

影响力最大化问题是在线社交网络中的热点问题,然而社交网络的结构错综复杂,传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足,利用有向超图刻画社交用户之间的群体影响,提出一种基于有向超图的预算影响力最大化问题.该问题是在有向超图的社交网络中,在给定预算下,寻找高影响力用户作为种子节点集,使得其最终的传播范围最大化.分析了该问题是NP-hard的且目标函数是非次模函数,提出了改进的贪婪算法和交换启发式算法进行求解,并分析了改进贪婪算法的近似比.通过将所提的算法应用到三个在线社交网络数据集中进行实验,验证了算法的正确性和良好性能.结果表明,改进贪婪算法基础上的交换启发式算法具有明显的性能优势.     

基于超图的非规则应用局部性优化

针对非规则循环应用中存在的一次迭代访问多个间接数组的问题,给出了超图数组的形式化描述,提出了三种基于超图的数据重排算法,即基于超图的非重复编码数据重排算法、基于超图的回溯搜索数据重排算法和基于超图的先划分再回溯数据重排算法,以及两种基于超图的迭代重排算法,即基于超图的非重复编码迭代重排算法和基于超图的回溯搜索迭代重排算法.通过对典型的非规则应用实例——流体力学问题进行实验,表明单独的重排算法提高程序执行速度约25.4%.在最好的数据重排与迭代重排的组合算法下,一级和二级高速缓存的平均命中率分别增加到91.7%和96.5%.     

一种向量划分的网络社团发现方法

为有效地检测复杂网络中的社团结构,对评估与发现社团的模块密度函数(即D值)进行了优化.通过模块密度函数的优化进程,展示了模块密度函数被优化到向量划分方法中的社团向量幅度最大化,并且提出了一种新的向量划分方法.在一个经典的真实世界网络中检验了该算法.实验结果暗示这种新的算法在发现复杂网络社团上是有效的.     

基于相邻节点聚类的社团划分算法

社团结构是复杂网络中的拓扑属性之一,具有同一社团内的节点连接紧密而不同社团的节点连接疏松的性质.作者基于复杂网络中的社团结构的性质并根据网络中相邻节点的距离关系,提出了一种社团划分算法--基于相邻节点聚类的社团划分算法.笔者对算法的基本概念以及实现进行了详细的描述,通过应用在实例上所得结果说明算法的可行性.     

基于多目标优化的符号网络社区检测算法

符号网络可以描述实体之间的多种关系,对符号网络中的社团检测可以挖掘出其中的有效信息.同时考虑连接密度和连接符号,将社团发现问题建模为一个多目标优化问题,基于MOEA/D框架,提出一种改进的符号网络社团发现算法,设计了基于字符串的编码方式、预分区策略、交叉合并策略、变异方式等.实验结果表明,本算法可以有效检测出社团结构.     

超图的可平面性算法

随着超图理论在实际问题中的深入应用,其平面性研究也更加具有意义.回顾了超图的一般理论,给出了超图的二部图概念,并在此基础上给出了超图的可平面性算法.该算法是多项式时间算法,是有效算法.     

与或图数据库的关系模式规范化算法

在图论基础上提出了与或图数据库。以与或图为描述工具的一种新的数据库理论 ,它使数据库的理论更加直观 ,算法更加简洁。给出了与或图数据库的定义、规范化理论、无冗余和既约化理论 ,证明了它与关系数据库的等价性 ;然后给出了依赖集存在冗余和既约的必要条件 ,讨论了无损分解在与或图形式下的特性 ,从而形成了与或图数据库关系模式分解的规范化算法。结合实例阐述了与或图数据库比关系数据库更加形象直观 ,便于理解学习 ,且为图论和人工智能各种算法在数据库应用中的引入奠定了相应的基础     

超图嵌入带权重圈的一个2-近似算法

超图嵌入带权圈(HEWC)问题就是把超图的超边以路的形式嵌入一个带权圈, 使得圈上任何带权连接边的最大阻塞最小。这个问题的一个简单形式是图嵌入带权圈(GEWC),即把普通图的边以路的形式嵌入 一个带权圈。HEWC问题第一次被归结为一个整数线性规划问题,并且利用LP的放松问题和有界启发得到一个近似解。 然后设计了一个非常简单有用的可以和LP近似算法得到一样好的近似解的线性时间近似算法。     

基于核方法的半监督超图顶点分类算法分析

分类学习算法的研究是计算机科学的研究热点,超图上顶点的分类问题作为一般图顶点分类问题的推广,被广泛应用于各种计算模型。对基于核方法的半监督超图顶点分类算法进行理论分析,给出算法的收敛性分析和广义界估计值。     

与或图数据库的可达算法和寻根算法

与或图数据库是利用与或图描述数据库的关系模式 ,从而建立起新的一套数据库理论。这种数据库理论采用图论作为数学基础 ,将可达算法、搜索算法和分块算法引入关系数据库 ,来解决规范化算法中关键字求解和依赖蕴涵的问题。该文提出了利用宽度搜索、深度搜索、分块搜索和启发式搜索四种搜索算法判断依赖蕴涵问题 ,以及利用生成子图的方法求解候选关键字的问题。最后进一步证明了这些算法在复杂度上比传统算法更加优越。由此可见与或图数据库的算法更加高效直观易于编程 ,还为图论和人工智能与数据库的结合提供了可能     

超图的分数着色和分数团

超图是最一般最复杂的离散结构,是图的自然推广,但是图中的一些定义和结论并不是都能轻而易举地推广到超图中.给出超图分数着色和分数团的定义,这与特殊情形下的图的分数着色和分数团的定义是相容的,并将图的分数着色和分数团的一些结论在超图中进行了推广.     

基于有权重超图的离群点检测

基于有权重支持度框架的关联规则挖掘算法和超图分割算法, 给出一种新的基于有权重超图模型的离群点检测算法WHOT(Weighted Hypergraph based Outlier Test). WHOT算法根据有权重支持度的定义, 重新设计了基于有权重支持度框架的关联规则挖掘算法, 并挖掘出数据集中的重要关联规则, 形成超图. 在超图上应用超图分割算法, 得到聚类集合, 再结合项权重和事务权重的定义, 判断一条记录是否为离群数据.     

超图 的一种特殊类型的分解

超图H是一个二元组(V,E), 其中V是有限集, V中的元素称为顶点, E是V的有限非空子集族,E中的元素称为超边.在过去的四十多年里, 图论已被广泛认为是解决几何、数论、运筹学和优化等领域中各种组合问题非常有用的工具. 为了解决更多的组合问题, 把图的概念推广到超图是非常自然的事情.从组合设计的角度, 用组合设计的方法来研究超图. 本文考虑一种特殊类型的超图分解. 通过引入辅助设计, 建立递推构造的方法.证明了当且仅当v≡1,2,6(mod 8)并且v≥6时存在S(3,W(3)4,v).     

一种基于有向超图的规则库冗余及环路检测方法

当规则库的规模随着知识的更新而不断增大,规则库的维护就变得日益重要.其中,规则库的冗余和环路是影响规则库效率的重要问题.针对含有复合规则的产生式规则库,提出了一种基于有向超图的规则库表达方法,定义了其邻接矩阵和可达矩阵并推导出可达矩阵的计算方法.在此基础上给出了基于可达矩阵的冗余和环路检测算法.与已有的基于有向超图的算法相比,新算法图更简洁,矩阵规模更小,从而检测效率得到提高.实例证明该算法是有效可行的.     

基于遗传算法的二部图判定算法

应用遗传算法来判定二部图的具体过程是首先将无向图G的节点随机分配到两个不同社区中,然后用遗传算法进行进化操作,优化无向图G的模块化函数Q,当Q取最小值且无向图G的边只存在于两个社区之间,则无向图G为二部图.实例分析结果验证了算法的有效性.