双网络中影响力凝聚子图发现算法

双网络由物理图和概念图构成,其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系;概念图中边表示结点间的相似程度,通常由计算得出.最近,从双网络中发现凝聚子图,即物理图中连通且概念图中稠密的子图受到研究者的广泛关注,在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此:1)提出一种基于最小边权重定义的影响力凝聚子图,即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒.2)由证明可知,发现影响力最大的k-ICT子图是NP-难的,因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图,能够根据不同的k值,快速发现包含所有k-ICT子图的候选子图.3)提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT,用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验,验证算法的高效性和有效性.

基于拓扑凝聚图的机会网络关键节点评估

评估机会网络的关键节点可以发现对网络吞吐量影响最大的节点,为网络的优化和维护提供支撑.为此,针对机会网络拓扑结构动态变化的特性构建了拓扑凝聚图,定义了二阶节点度、连接强度和关键域重要度3个评估指标,以指标的欧式距离表征节点的重要性.实验结果表明,与介数中心性方法相比,提出的模型具有有效性和优越性,并且模型在时间窗取20 min时具有较高的精度.

几类凝聚图的轮廓

设Ｇ是个图，｜Ｖ（Ｇ）＝ｎ｜对Ｇ上的任一个标号ｆ：Ｖ（Ｇ）→｛１，…，ｎ｝记，且当ｊ≠ｉ时，Ｇ中有边以ｆ（－１）（ｊ）及ｆ（－１）（ｉ）为两端点｝）．称Ｐ（Ｇ）＝ｍｉｎ｛Ｐ（ｆ）：ｆ是Ｇ上的标号｝为图Ｇ的轮廓．对以Ｗ表示Ｇ中Ｗ的边界．本文证明：ｉ）若Ｇ是凝聚图，ｆ及ｆ是Ｇ上一对互逆标号，则Ｐ（Ｇ）＝Ｐ（ｆ）的充要条件是ｆ为凝聚标号，且此时若Ｇ，Ｈ均是凝聚图，则存在阶梯标号。使得路、回、完全留之间的下列乘积图也是凝聚图。

二部图凝聚子图快速查询算法以及在电子商务中的应用

随着互联网的飞速发展,亚马逊,阿里巴巴和eBay这样的的电子商务平台已经成为世界经济不可或缺的一环。在这些电子商务平台中,用户和商品之间的互动可以自然地抽象成二部图,其中每个点表示用户或商品,每条边表示用户购买或评价了物品。如果一些用户和商品之间发生了紧密的联系,那么他们就形成了一个电子社区。基于二部图中的凝聚子图模型(α,β)-core,引入了(α,β)组的概念来代表社区。设计了有效且快速的算法来计算大规模用户-商品二部图中包含给定查询点的(α,β)组,给出了查询算法并分析了算法的时间和空间复杂度。在6个真实数据集上的实验证实了采用(α,β)组这一模型的合理性以及提出的算法的高效性。

面向部分向量化的循环分布及聚合优化

大量循环中都存在着少数无法向量化的语句以及许多可向量化语句,循环分布通常可以将这些语句分离到不同的循环中,进而实现循环的部分向量化。目前主流的优化编译器仅支持简单激进的循环分布方法,因而导致向量化后的循环开销过大,且不利于寄存器和cache的重用。针对上述问题,提出了面向部分向量化的循环分布及聚合方法。首先,分析了一般循环分布的两个关键问题:语句集的划分和循环执行顺序的确定;其次,提出了面向最大聚合的凝聚图结点排序方法来指导循环合并,在不影响并行性的前提下减小了循环开销;最后,通过实验对提出的方法进行了验证。实验结果表明,对于测试用例,提出的方法能够生成正确的向量化代码,并且能够显著提高向量化程序的执行效率。

M-矩阵的判定

M-矩阵是数值代数的一个重要研究课题。通过研究矩阵伴随有向图圈中所涉及到的量,得到了不可约矩阵是非奇异M-矩阵的一个新的充要条件,同时给出了一个将可约矩阵化为Frobenius标准型的图论方法,进而得到判定一个可约矩阵是否为非奇异M-矩阵的具体方法,即先将矩阵化为Frobenius标准型,然后判定对角线上各块是否是非奇异M-矩阵。最后通过一个实例说明所述的方法是可行的。

基于复杂网络的心绞痛血瘀证中药组方研究

作者基于中医临床文献数据,从临床治疗心绞痛血瘀证的方剂出发,使用复杂网络算法构建了中药网络,计算了中药的点中心度(degree)、中间中心度(betweenness centrality)和接近中心度(closeness centrality),以及使用凝聚子图CONCOR迭代相关收敛法分析了中药的聚类情况。结果发现丹参、川芎、黄芪、红花、赤芍的点中心度、中间中心度和接近中心度都较高,为治疗心绞痛血瘀证的核心药物。聚类结果显示,中药可聚类为27个子群,其中4个子群(中药组合)在中药新药处方筛选上有一定的应用价值。为了分析处方内部中药可能的配伍关系,作者对子群进行了二级凝聚子群分析,进一步计算了二级子群的密度,并结合中医理论给出了解释。结论:复杂网络算法可以有效辅助治疗心绞痛血瘀证中药组方的研究。

基于GN算法的文献聚类方法研究

文献是人类文化传播不可或缺的记录形式,文献结构研究的意义重大,有利于促进信息获取、知识交流和学术研究。本文将GN算法应用于文献聚类的研究当中,介绍了GN算法的步骤和文献聚类的过程,最后进行了聚类模型的演示,实验表明该文献聚类方法是有效的。

The Weak—Coupling of Bose—Einstein Condensates

The coherent characteristics of four trapped Bose-Einstein condensates (BEC) conjunct one by one in aring shape which is divided by two far off-resonant lasers, are studied. Four coupled Gross-Pitaevskii equations are usedto describe the dynamics of the system. Two kinds of self-trapping effects are discussed in the coupled BECs, and thephase diagrams for different initial conditions and different coupling strengths are discussed. This study can be used todetermine interaction parameters between atoms in BEC.