在线社会网络结构、演化及运行

在线社会网络结构、演化及运行

1社会网络的度异配性20世纪的繁荣和发展，加深了对世界极其复杂的社会系统的理解。近年来,随着信息技术的发展以及Web2.0技术的广泛应用,互联网上涌现出很多在线的社会网络。这些社会网络的规模异常庞大且时刻处于动态变化之中,因而需要将传统的社会网络分析和现代的复杂网络研究结合起来才有可能理解人与人之间相互作用的模式和动力学过程。在线社会网络的结构及运行其上的动力学过程,近年来已引起了不同学科研究人员的关注。研究Web社区中个体之间的关系及人的在线行为是近年来信息科学领域非常关心的问题。互联网上人与人之间的关系和相互作用可以用在线社会网络来描述,用户为节点,而用户之间的好友关系则为连边。我们重点研究了在线社会网络的结构、演化及运行其上的舆论动力学过程。对中国国内一个大型的在线职业人士社交网——若邻网(Wealink)进行了研究。发现该网络具有小世界特性、高聚类系数、层次化结构和社团性等与一般的现实社会网络相似的共性,同时也表现出了自己的特性:度分布具有无标度特性,连通子图规模分布、度分布和社团规模分布呈现出锯齿状以及度异配性。网络的功能对结构有显著的影响,通过模型阐明了该网络的度分布形成的机制,并探讨了在线社会网络度异配性的起源。我们还研究了Wealink的网络结构演化特性。研究发现其规模增长表现出非平凡的S型,进而为Web社区中的Bass扩散模型提供了一个例证。与传统的网络增长模型所预测的不同,真实网络的密度、聚类系数、异质系数和模块度随着时间的增长表现出非单调特性,且平均路径长度和直径出现收缩现象。特别地,首次揭示了在线社会网络从同配网络到异配网络的转变,并构建了一网络模型以阐明该跃变过程。针对Wealink中的用户行为的研究发现,发出的连接请求被快速地响应,互惠时间分布为指数分布。此外,邀请者/接收者的度值几乎与互惠时间无关。用户行为之间的时间间隔分布,即用户发出邀请之间、接受邀请之间或任意两个事件之间的时间间隔分布满足指数相同的幂律。我们研究了优先连接现象,发现对于优先接受、优先创建和优先依附3种情况,线性优先性均成立。我们研究了在线社会系统中个体的活动性和流行度。实证研究发现个体流行度或活动性的分布服从幂律或延拓指数分布,且活动性对人类动力学有显著影响,活跃度越高,用户行为的时间间隔分布越集中。我们构建了一概率模型阐述不同的活动性和流行度分布产生的机制,发现当优先性指数β=1即线性优先时为幂律分布,当0<β<1即亚线性优先时为延拓指数分布,而当β=0即不存在优先性时则退化为指数分布。研究了社会网络中基于社会影响的离散状态舆论动力学。初始时每个个体的状态可取离散值i=1,2,K,I。研究发现,对于任意的I≥2和自信参数,即个体维持当前状态的概率0≤u≤1,当u与个体度值无关时,状态为i的个体的加权比例〈qi〉为鞅,即状态为i的个体的总度值占网络总度值的比例〈qi〉的均值为一常数,状态为i的个体的比例qi随着时间的增长将逐渐收敛至〈qi〉,且随着网络度同配系数的增加,收敛趋势逐渐减慢。当u与个体度值相关时,〈qi〉不再是鞅,但qi仍收敛至〈qi〉。上述两种情况中,对于有限网络,所有个体的状态将最终达到一致。进一步研究了网络中存在状态不随时间变化的坚定型个体的情况,研究发现,当u与个体度值无关时,〈qi〉和qi均收敛至仅与初始时坚定型个体的分布有关的固定比例,最终的场景将是坚定型个体所处于的几种状态共存的平衡态。我们在无标度网络上的数值模拟验证了解析结果。该模型强调了度值大的个体对最终的一致态或共存态的影响,体现了社会网络中舆论扩散的一些现实特征。2蜂预防选取及控制算法牵制控制的基本思想是:通过有选择地对网络中的少部分节点施加控制而使整个网络具有期望的行为。因此,牵制控制涉及到的第1个基本问题就是可行性问题。这方面的研究目前主要集中在对部分节点施加线性反馈而使整个动态网络稳定在期望的同步状态。在理论方面已经清楚的是,只要网络的耦合强度和反馈控制增益合适,那么只需控制部分节点就能够实现控制目标。牵制控制的第2个基本问题是有效性问题,即如何选取受控节点才能使达到控制目标所花的代价尽可能小。这里的代价包括所需直接控制的节点数量、网络耦合强度和反馈控制增益幅值等。已有的研究表明,利用网络的拓扑特性,有选择地对网络中少量重要的关键节点直接施加控制要比随机选择部分节点加以控制具有明显优势。我们近期的研究主要集中于把牵制控制的思想用于蜂拥控制。从复杂网络的观点看,蜂拥行为可以看作是拓扑结构随时间变化的动态网络所产生的协调一致的行为,而目前关于复杂动态网络牵制控制的研究则主要针对的是具有固定拓扑结构的网络。目前在蜂拥控制研究中采用最多的是1986年Reynolds提出的一个用计算机来模拟蜂拥群体行为的经典的Boids模型。这个模型中的自主体(Agent)满足3条基本规则:1)分离(Separation):与邻域内的自主体避免相撞;2)聚合(Cohesion):与邻域内的自主体保持紧凑;3)速度匹配(Alignment):与邻域内的自主体速度保持一致。为了能够保持分离,一个自主体首先需要获得邻域内其它自主体的位置信息。对于一个自主体来说,每一个在其邻域范围内的自主体与它之间有一个排斥力,这个排斥力是与它们之间的距离成反比的。每一个自主体所受到的排斥力是它邻域范围内其它自主体对它的排斥力的累加。为了能够产生聚合的群体行为,一个自主体需要计算出邻域内其它自主体位置的平均值,由此产生一个作用于该邻域内所有自主体的吸引力,这样使自主体向平均位置方向运动。为了能够实现速度匹配,每个自主体需要获得邻域内其它自主体速度信息,计算出邻域内自主体的平均速度。通过速度匹配,可以使自主体速度大小和方向与这个邻域内所有自主体速度的平均值保持一致。2006年,Olfati-Saber提出了3个蜂拥控制算法。其中,第1个控制算法体现了Reynolds的3条规则,第2个控制算法具有避免与障碍物相撞的功能。第3个控制算法通过对每个自主体添加引导反馈来实现跟踪目标的功能。但是,在第2个控制算法中假设每个自主体都知道虚拟领导者的信息,这种假设的好处是保证每个自主体都能够聚合和达到期望的速度。然而,这个假设和自然中的一些实例是不相符合的,而且它在工程实际中有时也是很难实现的。在自然界,群体中往往只有很少的个体具有引导信息,比如食物所在的位置或者迁移的路线等等。例如:研究发现鱼群中只有少量鱼具有迁移的路线信息,但是它们能够引导整个鱼群游向期望的地点;蜂群中只有大概5%的蜜蜂知道新巢的信息,并能引导整个蜂群飞向新巢。最近,Couzin等人针对这种现象建立了一个离散模型,并通过仿真得到群集中只需要很少一部分个体知道引导的信息,就可以使绝大多数个体具有期望的群集行为。针对上述现象并受到复杂网络牵制控制研究的启发,我们假设群体中只有一部分自主体具有虚拟领导者的信息。我们将所有的不具有引导信息的自主体分为两大类。在无限个连续、非空和一致有界的时间间隔中,如果某个不具有引导信息的自主体始终存在一条联合路径连接它和某个具有引导信息的自主体,就称该自主体为第Ⅰ类不具有引导信息的自主体;否则,就称它为第Ⅱ类不具有引导信息的自主体。我们假设如果存在一个足够大的时间T,当t≥T时,第Ⅱ类不具有引导信息的自主体和具有引导信息的自主体之间不存在任何联合路径。这个假设暗示了如果一个不具有引导信息的自主体与具有引导信息的自主体有足够长的时间没有直接或间接的连接,我们就认为它们之间永远不会直接或间接相连。在这个假设条件下,当t≥T时,所有具有引导信息和第Ⅰ类不具有引导信息的自主体,都不会直接和间接受到第Ⅱ类不具有引导信息的自主体的影响。我们从理论上证明了,所有具有引导信息和第Ⅰ类不具有引导信息的自主体的速度将会渐近收敛到期望的速度。此外,我们在蜂拥控制方面也做了进一步研究,具体包括:1蜂预防控制算法针对以往所有具有虚拟领导者的蜂拥控制算法都是针对单个虚拟领导者的情形,我们首次提出了具有多个虚拟领导者的蜂拥控制算法,我们理论上证明了该算法可以使所有智能体准确跟踪各自需跟踪的虚拟领导者,并且证明了所有智能体的位置和速度的平均值指数收敛到所有虚拟领导者位置和速度的加权平均值。2保持网络连通性我们提出了一个具有保持网络连通性的蜂拥控制算法,该算法在完成所需的蜂拥控制目标的同时具有保持网络连通性的功能,即该算法只需要初始网络为连通就可以完成所需的蜂拥控制目标。另外,我们还研究了带有一个虚拟领导者并且保持网络连通性的蜂拥控制算法。在初始网络为连通的情况下,该算法可以使所有智能体准确跟踪到虚拟领导者,并且智能