基于两种子结构感知的社交网络Graphlets采样估计算法

graphlets是指大规模网络中节点数目较少的连通诱导子图,在社交网络和生物信息学领域有着广泛的应用。由于精确计数的计算成本较高,目前大多采用随机游走采样算法来近似估计graphlets的频率。随着节点数目的增多,graphlets的种类数增长迅速且结构变化复杂,快速估计大规模网络中所有种类的graphlets的频率是一项挑战。文中提出了基于两种子结构的随机游走采样算法CSRW2来估计graphlets频率,即给定graphlets节点数k(k=4,5),通过采样k-graphlets的子结构(k-1)-path和3-star得到两种样本,之后用比例放大法综合,以高效估计graphlets并适应graphlets结构的复杂变化。实验结果表明,CSRW2能以统一的框架估计所有k-graphlets类型的频率,其估计精度优于现有代表性算法,更适用于频率较低且结构较稠密的graphlets。例如,用CSRW2估计真实网络sofb-Penn94中的5-graphlets,当样本数为2万时,标准均方根误差的平均值由WRW算法的0.8降低至CSRW2算法的0.22左右。

Graphlet Degree Vector方法的优化与并行

Graphlet Degree Vector(GDV)是一种研究生物网络的重要方法,能揭示生物网络中各节点与其局部网络结构的相关性,但随着需要挖掘的自同构轨道数量的增加以及生物网络规模的增大,GDV方法的时间复杂度会呈指数级增长。针对这个问题,在现有串行GDV方法的基础上,实现了基于消息传递接口(MPI)的GDV方法并行化;此外又将GDV方法进行了改进并将改进后的方法实现了并行优化,改进后的方法在寻找不同节点自同构轨道的过程中优化了计算过程以解决重复计算的问题,同时结合负载均衡策略合理分配任务。模拟网络数据和真实生物网络数据上的实验结果表明,并行化的GDV方法与改进后的并行化GDV方法都具有较好的并行性能,并且对不同类型不同规模的网络都具有较强的适用性,扩展性强,可有效地保持寻找网络中自同构轨道的高效率。

基于图元向量的差异共表达分析研究

差异分析对于揭示生命体的生长、发育和衰老过程及疾病发生具有重大的意义,基于网络的差异分析方法已经成为系统生物学的一个研究热点.Przulj提出的图元及图元向量作为一描述网络局部结构信息的方法,已经在网络分析方法面取得了很多重要的结果.本文在图元向量的基础上提出了二种节点变化的差距度量方法,通过聚类可以分别挖掘网络中模块内变化基因簇和模块间变化基因簇.应用AGEMAP数据库中12个小鼠组织基因表达数据的结果表明:大部分聚类簇都高度显著富集与衰老相关的CO条目.

基于子图模式的网络流量分类方法研究

盲分类(blind classification,BLINC)方法提出利用不同网络应用在传输层子图连接模式的差异对网络流量进行分类,获得了良好的效果,该方法分类的准确度较高,但是完整度则相对较低。为了解决BLINC分类完整度较低的问题,借鉴BLINC的分类思想,提出了基于子图模式的流分类方法,该方法综合运用源节点子图模式、目的节点子图模式和端口分析技术。实验证明,在同样阈值的条件下该方法对同样一组Web、DNS、Mail、FTP、P2P流量数据进行分类,准确度与传统BLINC方法基本保持一致,但是完整度得到了明显的提高,具有很好的实用性。

比较图元向量和点的聚类系数对差异网络的研究

差异分析对于揭示生命体的生长、发育和衰老过程及疾病发生具有重大的意义,基于网络的差异分析方法已经成为系统生物学的一个研究热点。网络节点往往通过与局部结构作用实现某种功能,其与局部结构的关系变化,很可能影响其功能。本文利用仿真实验的方法比较了图元向量和点的聚类系数两种局部结构测度的性能,并且利用他们分别设计算法挖掘差异网络中模块化变化的基因簇。应用AGEMAP数据库中小鼠12个组织基因表达数据进行实验,大部分聚类簇都高度显著富集与衰老相关的GO项。

基于复杂网络的层次性研究

自然界和人类社会中存在各种各样的复杂系统,这些系统由许多相互连接的单元构成,而网络是描述复杂系统最自然的工具。通过形态空间网络的层次性量化:树状性、前馈性和顺序性,可以很好的探究网络本身及其内部的结构特征演化。应用可视图算法,研究FBM和维基百科投票管理人的职位晋升网的层次演化。得出:不同网络的形态和内部演化不同,但也有相似性。FBM的网络形态相对稳定呈现蝴蝶状,前馈性和顺序性呈现趋势性变化。维基百科投票网络,前馈性与分数布朗运动呈现相同趋势,但顺序性相对稳定,小幅度的波动,并且树状性不同于FBM,从反椎体到蝴蝶状最后演变成椎体。

大规模网络图中4节点子图数量快速估计算法

针对大规模网络图中存在的大量4节点子图数量难以精确统计分析的问题,提出了一种大规模网络图中4节点子图数量快速估计算法(SmartMoss)。该算法通过随机变量方差分析技术对比3路径采样算法(3PS)和中心3路径采样算法(C3PS)两种前沿算法的估计误差得出其各自不同的适用范围,进而通过计算被测网络图权重密度分布与误差实时选择使用3PS算法或C3PS算法对网络图中4节点子图进行快速采样,通过采样比例混合3PS算法与C3PS算法的估计结果实现对网络图中各4节点子图出现数量的快速估计。实验结果表明,在同等估计误差下提出的SmartMoss算法比已有3PS算法和C3PS算法快10倍以上。SmartMoss算法可以实现对大规模网络图中4节点子图数量进行快速准确的估计,同时为网络社团演化和恶意代码检测等实际应用提供一定的理论参考。

融合多重特征的噪声网络对齐方法

针对网络对齐任务中网络结构差异大和锚节点对噪声大的问题,提出一种基于多轮迭代的网络对齐方法。该方法在每轮迭代时使用多种启发式方法计算不同维度的节点特征,利用多重特征的组合来评估锚节点的可靠性,过滤其中潜在的噪声,增强每轮对齐过程的置信度;使用图神经网络增强无属性节点之间的一致性,减轻网络结构差异带来的影响。实验结果表明,该方法可以在高噪声的情况下具有高准确率,验证了其有效性。