摘要 合作博弈中的参与人只将合作、不合作作为自己的策略,而双合作博弈是合作博弈的一般化,参与者以合作、不合作和弃权作为自己的策略,以获得自己所在的联盟利益的最大化,从而使自己的收益达到最优.与合作博弈一样,如何分配参与者联盟获得的总收益是双合作博弈的一个重要研究问题.本文利用矩阵半张量积工具,研究了双合作博弈的Shapley值计算问题.首先构造了双合作博弈的Shapley矩阵,然后将双合作博弈的Shapley值计算转化为双合作博弈的特征函数矩阵与Shapley矩阵乘积形式.本文得到的Shapley值矩阵计算公式形式简洁,不但简化了计算,而且为双合作博弈的研究提供了新的工具.

摘要 在生物医学大数据时代,如何全面有效地发现致病基因、药物靶标等关键要素,从整体上理解宏观表型的微观本质,是目前信息科学与中西医学交叉研究面临的重大共性挑战之一.生物系统是典型的复杂系统,克服上述挑战的关键是:如何通过深入理解复杂生物系统的“关系”本质,解决复杂系统多层次信息融合难题以及生物医学大数据中广泛存在的维度高、噪声大、样本少等难点.“生物网络”是构成复杂生物系统的基础,反映人体内部基因和基因产物等各种生物分子的相互关系、生物分子与疾病和药物等不同层次的关系,生物网络已被广泛用于生物医学大数据的分析.李梢课题组从20余年前开始中西医药与生物网络的关联研究,率先提出“网络靶标”假说,并进行方法构建与应用.本文对基于生物网络的关系推断理论与方法进行总结与思考.首先,从原理上,发现疾病宏观表型与微观分子在复杂生物网络中存在“层次模块化关系”,即宏观层次的涌现在微观上具有局域模块性,宏观表型越相似,微观致病基因或药物靶标在网络上的模块性关联越强.其次,从方法上,给出基于生物网络从生物医学大数据、少量目标样本中推断关键生物要素的“关系推断”一般性方法框架:以层次模块化关系为基础,从全局角度进行关系网络构建、关系表示与建模、未知关系推断,实现关系的实体化、数学化、整体化.进而,从应用上,基于生物网络的关系推断方法在致病基因与药物靶标预测、疾病标志物识别、中医药机制解析等方面表现出很好的性能.综上,关系推断方法能够为从系统角度和分子水平揭示中西医药科学原理提供系统解决方案,也为网络药理学等新兴学科提供重要的原理和方法学支撑.

摘要 多层网络的结构和动力学是目前网络科学研究中的前沿方向.在多层网络中单层之间的连接方式直接影响整个多层网络的动力学、传播、扩散和同步.对于多层网络的一般结构,目前还没有系统的理论和方法,人们只能从简单的多层网络结构入手,来探索层间连接如何影响多层整体动力学行为.本文的工作针对单层是链状结构的双层网络,通过图论理论和数值计算探讨这一问题,寻找层间连接的优化方式.首先,根据主稳定函数方法,在同步域无界的条件下证明了各层结构相同的多层网络在任意层间部分连边方式下,均存在层间耦合强度阈值,使得整个网络同步能力达到最大,且最大同步能力就是其单层网络的同步能力.其次,仿真得到双层链状网络在层间两条连边下的最优连边位置分别为各条链的1/4和3/4处;最差连边位置分别为其端点及相邻次端点处.本文还分别利用主稳定函数方法以及"网络最短距离"结构指标,细致地讨论了单层节点数分别为4N, 4N+1, 4N+2, 4N+3情况下的层间最优连边方式.结果表明:单层节点数4N对应有4种层间最优连边方式,其他3种情况下层间最优连边方式均唯一.最后,本文提出了最优层间耦合强度的表达式,并通过计算不同节点数情况下网络的最优层间耦合强度,验证了该表达式的正确性.

摘要 定量评估城市轨道交通站点的重要性有助于优化城市轨道交通网络,提升针对突发事件的应急管理能力.现有工作常根据轨道拓扑结构或静态客流的分布来识别关键站点,然而,由于居民日常出行行为展现时空变化特征,它们对关键站点的识别也有重要影响.为此,本文提出一种结合轨道网络拓扑结构和动态客流的拓扑–客流中心性指标来动态识别轨道交通关键站点.首先,将轨道交通网络拓扑结构抽象为节点负载网络,利用节点负载刻画客流时变特征.其次,利用级联失效模型对比拓扑–客流中心性指标与其他中心性指标对网络平均效率、极大连通系数和损失客流的影响.大量实验表明所提指标能有效识别轨道交通网络中的关键站点.同时,关键站点会随客流演变展现出动态变化特征,特别是当客流量波动剧烈时最为显著.

摘要 在复杂网络研究领域,社区隐藏算法旨在破坏社区发现算法的有效性,从而隐藏用户之间的关系,达到保护用户隐私的目的.现有的社区隐藏算法寄希望于已有用户改变自己的社交关系实现该目标,这对用户影响较大,操作空间比较小.不同于此类算法,本文所提的算法从增加节点及其相应边的角度出发,即伪造用户及其关系,最大程度降低了对用户的影响,将社区隐藏问题转换为网络增长问题.首先基于ratio association和ratio cut,提出两种更适合社区隐藏的指标;然后基于强化学习框架,定义动作空间为不同的网络增长模型,将两个指标在l个阶段的一致性策略值作为网络的状态表示,并将指标值作为奖赏值;最后采用两种策略来对指标进行优化,即给每个Q函数赋予权重的标量化多目标Q-learning算法以及基于Pareto最优算法的多目标Q-learning算法.在真实数据集上的大量实验表明,相比于现有最新的社区隐藏算法,本文所提算法展现出更好的有效性.

摘要 链路预测任务是根据已知的网络结构和节点属性等信息来预测网络中产生新链路的可能性.它是网络科学中的一个基础性问题,具有重要的理论研究和实际应用价值.近年来,网络表示学习领域的学者利用深度学习提取网络复杂特征,大幅度提高了链路预测效果.实际网络中节点具有局部聚类现象,然而,当前的网络表示学习侧重于提取网络全局特征,忽略了局部信息特征.针对这个问题,我们提出了能够学习网络中节点在不同社区中局部特征表示的模型network-splitter.该模型利用重叠社区思想,在每个社区中创建节点的一个角色副本,并学习该角色副本的特征表示.最后将节点在不同社区中对应的角色副本信息通过神经网络综合,得到的综合向量包含网络全局特征和节点局部特征,并可应用到链路预测任务中.本文的实验结果表明, network-splitter模型与最新的网络学习表示方法相比具有很强的竞争力.

摘要 在高铁日常运营中,地质灾害或设备故障等突发事件导致铁路行车区间中断,长时间的区间中断通常会导致大面积的列车晚点,给旅客出行带来极大的延误,如何在区间中断下对列车进行实时调整是高速铁路调度运行的一项重要课题.本文针对固定时间的区间中断,构建了列车运行速度调整和运行图调整的混合整数非线性规划(mixed integer nonlinear programming, MINLP)模型.在该模型中,除了常见的取消车次和延迟发车调度策略,还将降速运行策略考虑在内,在满足行车安全和车站通行能力的约束条件下,以3种调度策略的加权延误影响最小化为目标.该模型基于列车运动学模型计算列车降速运行带来的延误时间,并通过移动闭塞原理控制列车运行安全间隔.本文建立的模型可由商业优化软件CPLEX直接求解,并保证运行调整方案的实时性.模型还讨论了取消车次、延迟发车和降速运行这3种调度策略对总延误时间的影响,最后以京沪高铁实例进行验证.验证结果表明该模型是合理有效的,通过模型求解能对实际问题给出合理的调度方案并提高列车终到正点率.