面向社交网络基于协作度协商的联盟形成机制

胡 军，张振兴，邹 立

(1.湖南大学 信息科学与工程学院, 湖南 长沙 410082；2. 桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004；3.南京大学 计算机软件新技术国家重点实验室, 江苏 南京 210093；4.湖南大学 嵌入式与网络计算湖南省重点实验室，湖南 长沙 410082)

面向社交网络基于协作度协商的联盟形成机制

胡 军1,4†，张振兴1,2，邹 立1,3

(1.湖南大学 信息科学与工程学院, 湖南 长沙 410082；2. 桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004；3.南京大学 计算机软件新技术国家重点实验室, 江苏 南京 210093；4.湖南大学 嵌入式与网络计算湖南省重点实验室，湖南 长沙 410082)

分布式多Agent构成的社交网络通常表现出不同的特征，针对不同的社交网络和多Agent本身的异质性，提出了一种面向社交网络的基于协作度协商联盟形成机制.该机制依托多Agent构成的社交网络环境，建立面向分布式环境的分布式协商协议，并设计一种考虑到社交网络特征和Agent异质性的基于协作度的协商策略，采用分布式自动协商方式形成联盟.通过对全连通网络、层次网路和小世界网络的仿真实验结果表明，该机制能够有效地实现分布式环境下的联盟形成，并且在反应大多数实际应用环境的小世界社交网络中表现出相对较好的性能.

多Agent系统；联盟形成；分布式自动协商；社交网络；协作度

形成联盟是多Agents最常用的一种协作方式，高效的构建联盟是多Agent系统中的研究热点之一.目前的联盟形成方法存在着诸多的局限.一是，大多数方法针对多Agent全连通的情况，未考虑实际环境中Agents之间不同的连接结构，适用面较窄；二是，现有研究中大多是针对集中式系统的，不适用于分布式的应用情况，实用性不强；三是，忽略了不同Agent的异质性，没有考虑Agent的协作态度和协作资源的不同，实用性不强.如文献[1-4]中Agent之间都是全连通的，求解联盟的方法是通过搜索联盟结构图获得最优联盟结构.这样联盟形成的过程是一个NP难问题，而实际应用中全连通的Agent情况并不多见.文献[5-6]引入了社交网络和学习型协同图的概念，使得问题的求解简化，但是文中没有考虑不同的网络拓扑结构对联盟形成的影响.集中式环境中，文献[7-9]先通过协商形成候选联盟集，然后通过发起联盟的集中管理者Agent分配效用，确定最终联盟.针对分布式应用环境，文献[10]中建立了一套基于协商的联盟形成机制，Agent在分布式协商协议下形成联盟和确定效用值的划分并且对比了不同网络拓扑结构对联盟形成的影响，但是该机制没有考虑不同Agent的协作资源和协作态度的不同的异质性，使得联盟形成效率相对不高.为了解决现有研究中的局限性，本文试图建立一套在分布式环境下、面向社交网路结构的，异质的多Agent联盟形成机制.本文首先对比分析全连通的、随机树型的、小世界网络社交网络拓扑结构特点；然后针对分布式应用环境，构建一个分布式的协商协议来保障联盟形成；接下来考虑邻居Agent的历史信任度和资源拥有情况下引入了协作度的概念，来体现不同Agent的协作资源和协作态度的差异性，进而表达不同社交网络结构的特点，建立一种基于Agent协作度的协商策略；最后，实现面向社交网络的基于协作度协商联盟形成机制SOCNCF(social networks oriented collaboration degree based negotiation coalition formation mechanism ).

1 社交网络

分布式环境中，多Agent之间的连通关系构建的网络拓扑结构图，可以看成是多Agent之间的社交网络SN(Social Network).该网络结构构成多Agent通过分布式协商形成联盟的环境基础.

1.1 简单的社交网络

设AGENT={Agent1,Agent2,…,Agenti}，表示一个用于联盟形成的Agents集合，Agents连通关系的网络拓扑图G=(A,E).A表示不同的Agent，E表示连接Agent的边，把可以与Agenti直接通信的其他Agent定义为Agenti的直接邻居，其形式化的定义如式(1):

I(i)={i'|(i',i)∈E,i'≠i}

(1)

例如，e=(1,2)∈E表示的意思是Agent1和Agent2之间是连通的，他们可以通过协商形成联盟.

传统的联盟形成机制中很少考虑到成员Agent的SN差异性，大多考虑的都是全连通的情况.但是实际应用中Agent是处于不同的SN中的，Agent之间的交互将受到SN的差异性限制.图1是使用本文实验平台产生的3种简单的社交网络，可见，图1(a)中可能形成的联盟是{Agent0}，{Agent1}，{Agent2}，{Agent0，Agent1}，{Agent0，Agent2}，和{Agent0，Agent1，Agent2}.可见联盟{Agent1,Agent2}是不可能形成的，因为Agent1和Agent2没有之间相连，他们之间不能相互交互协商形成联盟.在图1(b)中由于Agent之间的连同关系变了，所以不能形成的联盟是{Agent0，Agent2}，{Agent1，Agent3}.最后，在如图1(c) 的全连通图中，由于每一个Agent之间都是之间相连的，所有{Agent0，Agent1，Agent2，Agent3}的任意子集都可能形成联盟.

1.2 几类典型的社交网络

1.2.1 全连通网络

全连通网络中Agents之间都是全连通的，其联通关系如图1(c)所示，此时I(i)={i'|i'∈AGENT,i'≠i}.在这种网络中，每个Agent的直接邻居数目是相同的，也就是说每个节点的度数是一样的，各个节点之间就有对称性.

1.2.2 树型网络

树型社交网络是具有层次结构的社交网络，是通过随机选择节点的生成方式构建的树形结构.在随机树型的社交网络中，最典型的特点就是不同层次的Agent所具有的邻居数目|I(i)|差异性大.如图2所示，上层的Agent具有更高的连通性，而下层的Agent连通性比较差，叶子节点只有一个直接邻居.

(a)

(b)

(c)

图2 随机树社交网络

1.2.3 小世界网络

小世界网络一类特殊的复杂网络结构，在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达.这反映的是现实世界中陌生人可以通过彼此共同认识的人而连接的现象.

小世界网络的判定准则有两个，分别是特征路径长度和高集聚系数.网络的特征路径长度是指在它的图表示中，两个节点的路径长度的平均值(这里路径长度指两节点间最短路径的长度).许多复杂网络尽管节点数目巨大，但节点之间的特征路径长度则非常小[11].集聚系数则是用来描述“抱团”现象的，也就是“你朋友之间相互认识的程度”.从数学的角度上来说，一个节点的集聚系数等于与它相连的节点中相互连接的点对数与总点对数的比值.高集聚系数实际上保证了较小的特征路径长度[12].图3是由100个Agent形成的小世界网络，其中最大度数为10，平均度数为5.8.由图可以看出，小世界网络有明显的“抱团”现象，并且有边将这些“团”连接起来.

图3 小世界型社交网络

2 分布式协商模型

本文是使用分布式协商的方法形成联盟，所以首先介绍分布式协商的形式化模型基础；接下来叙述分布式协商要素；最后给出分布式协商协议.

设Agenti拥有一个特定的资源ri，ri描述的是这个Agent执行任务时可以利用的资源；把Agenti的直接邻居所拥有的资源称为Agenti的备用资源.当Agenti无法单独完成某些特定的任务时，Agenti可以使用自己的备用资源，通过与其直接邻居形成联盟来完成.Agent集合中的各个Agent可能形成的联盟是C1,C2,…,Cn∈2I，Ci中每个成员Agenti拥有ri所描述的资源，这样联盟Ci拥有的资源描述为rC∈∏i∈Cri.形成联盟Ci后可以得到一个整体的效用V(rC)∈Z+，这个效用代表的是联盟在系统中产生的效用值；通过协商，每一个成员Agent可以在这个效用值中划分到一份效用值vi∈Z+，易见∑i∈C=vi=V(rC).并且整体效用可用式(2)计算：

V(rC)=|C|∑i∈Cri

(2)

可见，形成的联盟越大，获得的联盟效用越大.

2.1 协商要素

分布式协商中的协商要素包括协商提议、协商区间和协商决策函数，这些都是构建分布式协商的前提.

2.1.1 协商提议

Agenti可以通过发送提议的方式向I(i)合适的Agentj发出联盟邀请，协商提议定义为式(3)所示：

(3)

2.1.2 协商区间

所谓协商区间就是协商双方的协商的效用分配的波动区间，即最小效用和最大效用.假如Agenti已经收到了Agentk∈Ι(i)∪{i},k≠j的提议(rC,vi)，如式(4)所示的等式表示对是Agentj加入该联盟后增加的效用：

δV(rC,rj)=V(rC,rj)-V(rC)

(4)

因此Agenti能够得到的最大效用如式(5)所示，其中vi是Agentj加入联盟之前Agenti所获得的效用分配，δV(rC,rj) 由式(4)求得，即Agenti很自私的全部占有Agentj加入增加的效用.

(5)

要衡量Agenti的最小效用就要计算当前Agenti的最好的效用值，Agenti将到目前为止可以加入的最优联盟的提议定义为o*=maxo∈commitsetiv(o)，其中，commitseti表示Agenti当前可以加入的联盟提议集合.因此Agenti的最小效用如式(6)所示，即协商区间的最小值不能小于Agenti到目前为止取得的最大效用：

vmin(rC,rj)=max (0,vi(o*))

(6)

2.1.3 协商决策函数

协商决策函数是Agent在收到协商提议后的按照最大化自身利益的原则决策自身行为的过程.

(7)

综上，Agent的决策函数定义如式(8)所示，即：

(8)

可见一个Agent进行协商决策的过程就是产生不同类型的提议，有：接收提议、反提议、新建提议等.

因此，Agenti可以执行的决策有：

根据协商策略就当前收到的提议产生反提议；

发送一个提议给当前可加入的最优联盟的邀请者Agent，加入该联盟；

2.2 分布式协商协议

协商协议通过对分布式协商通信过程的规定和Agent协商状态的定义，来实现协商过程的收敛性和避免死锁.

协商中的Agentj的状态定义为：sj={DONE,WAIT(i),SLEEP}.其中，DONE状态表示Agentj已接受某个协商提议，该Agent的协商已完成.WAIT(i)状态表示Agentj已向Agenti发送了协商提议，等待i的回复.SLEEP状态表示Agentj的初始状态，等待其他Agent发送提议过来.

具体协议流程如图4所示，开始形成联盟前，所有的Agent都处于SLEEP状态，当Agentj发送提议给Agenti∈I(j)后，邀请者Agentj将sj设置为WAIT(i)状态，此时I(j)/{i}中所有的Agent不能再发送新的提议给Agentj，避免死锁发生.此时唯一能和Agentj通信的只有Agenti，Agenti将发送给Agentj反提议、接受Agenti或者拒绝提议.如果Agenti接受了Agentj，Agenti将si设置为DONE.此时，Agenti将其自身的状态通知给正在等待它回应的主体.如果该提议包含该邻居，它发送接受提议消息给该邻居，如Agentj，对其他主体发送拒绝消息，之后Agenti将不能再收到任何提议.同时Agentj将Agenti加入保证可以加入的联盟集commitsetj中，Agentj将sj设置为SLEEP，表示现在Agentj可以接收新的提议；如果Agenti发送反提议给Agentj，Agentj将sj设置为SLEEP，Agenti自己将si设置为WAIT(i)；如果Agenti发送拒绝提议给Agentj，则Agentj将sj设置为SLEEP.本协议是通过避免产生提议环和避免提议冲突，来实现协商过程的不死锁性的.具体来说，通过下列通信的规则来实现：

图4 分布式协商协议中Agent状态迁移图

3 基于协作度的协商策略

3.1 协商策略函数

本文提出基于协作度的协商策略CBNT(CooperationDegree-BasedNegotiationTactic)，协商策略函数如式(9)所示指数函数族来逐步产生让步后的新提议.

(9)

3.2 协作度

本文引入了协作度的概念，来描述Agent的协作资源和历史协作状况的不同，从而体现在不同社交网络结构的差异性，进而通过协作度对协商态度值产生影响，来实现不同策略的协商过程.

定义1Agentj相对Agenti的历史协作度：

(10)

其中，分母是Agenti和Agentj所有历史交互提议的次数，分子是Agenti和Agentj所有历史交互协商成功的次数.反应历史协商过程中Agentj接受Agenti提议的几率，称为Agentj相对Agenti的历史协作度，反应的是Agent的协作态度.

定义2 Agentj相对Agenti的现在协作度：

(11)

分子是Agenti的邻居Agentj拥有的备用资源数量，分母是Agenti所有的邻居拥有的备用资源总和，当Agentj相对Agenti的其他邻居而言拥有更多的备用资源时，我们认为Agentj相对Agenti的现在协作度较高，反应的是Agent的协作资源.

定义3 Agentj相对Agenti的协作度：

cij=a×cij-past+b×cij-now∈[0,1]

(12)

Agentj相对Agenti的协作度是综合考虑定义1和定义2中的历史协作度和现在协作度的，式中a+b=1恒成立.a和b的选择反应的是联盟形成中更注重历史表现还是现在的资源占有情况.

基于上述协作度的定义，Agenti对Agentj的协商态度值采用式(13)计算：

(13)

4 SOCNCF机制

SOCNCF机制在分布式协商模型的基础上使用基于协作度的协商策略进行联盟形成，分布式协商模型保证算法的收敛性，基于协作度的协商策略保证算法的高效性.SOCNCF机制实现算法如算法1所示.算法开始阶段会产生模拟分布式环境的不同类型的社交网络，同时对Agent的协作度初始化；每一次联盟形成过程开始前会利用前一次联盟形成计算出的协作度cooperationTemp作为本轮的初始协作度；然后开始多轮协商进行联盟形成，在遵循社交网络和分布式协商协议的前提下得到协商决策函数Decision；根据得到的不同Decision对用来计算Agent之间协作度的相关参数进行计算和对Agent的状态进行更新，一遍联盟形成后根据Agent之间协作度的相关参数计算协作度并保存至cooperationTemp.然后开始下一次联盟形成过程，直至MAXHISTORYTIMES次后算法结束.

算法1 SOCNCFAlgorithm()

SOCNCFAlgorithm(){

graph = graphGen.getGg();

//产生Agents的社交网络，初始化当前协作度

cooperation=cooperationInit();

//Agent历史协作的初始化

cooperationTemp;//用来保存历史协作度记录

for times:1→MAXHISTORYTIMES

//利用协作度的动态更新进行

MAXHISTORY-TIMES次联盟形成

allAgents=initialiser.createAgents();

//Agent集初始化

cooperation=cooperationTemp;

//将上一轮的协作度记录赋给本Agent

for clock:1→MAX_TIME

//进行最大轮数不超过MAX_TIME的协商

for agent:allAgents

//遍历Agent集中所有的agent

if(agent.issleep&&!nonwaiting.isEmpty)

//判断Agent自身和邻居的状态

Decision=agent.getDecision();

//根据决策函数进行该Agent协商、决策

updateCooperationParameter(Decision，Parameter)//更新用来计算协作度的参数

updateState(Decision)

//根据得到的决策更新Agent的状态

sortNeiberhour(cooperation)

//根据Agent不同邻居的协作度的大小对邻居进行排序，下轮协商时将优先选择协作度高的Agent

endif

endfor //遍历完所有的Agent

endfor //本轮协商结束

CalculateCooperation(cooperationTemp, Parameter)//根据本次联盟形成的协作度

endfor//基于协作度的多次联盟形成过程结束

}

5 实验分析

5.1 实验设置

实验使用Eclipse平台仿真多Agent联盟形成过程，试验中模拟的机制有本文的SOCNCF和文献[10]社交网络中的联盟形成机制CFMSN(Coalition Formation Mechanism In Social Network)，文献[10]中所述的联盟形成机制是单纯的考虑Agent之间的连通关系—协作资源，忽略了Agent之间在协作态度上的异质性.实验内容包括两部分，第1部分将对比使用不同的社交网络时SOCNCF机制和CFMSN在总共使用的协商轮数上的差异性，由于SOCNCF机制需要历史信息的累计，故进行了10次联盟形成的过程，分别是CFMSN，SOCNCF-2，SOCNCF-3，…，SOCNCF-10，可见第1次联盟形成实际上就是没有使用协作度信息的CFMSN机制；实验的第2部分将在平均协商轮数、协商成功率、平均联盟大小、平均个体效用等4个方面对比分析以上两种方法在不同的社交网络下形成联盟时的性能，由于我们的实际应用中大多的多Agent联盟形成环境都是小世界网络拓扑结构，所以我们期望SOCNCF机制相比CFMSN机制来说在小世界网络中有更好的性能.

为了对比不同网络拓扑结构和不同规模Agent集下SOCNCF机制的性能，Agent社交网络环境设置有两种，为了保证不同网络拓扑结构的可比性，第1种社交网络环境中将网络的最大度数都设定为20；第2种社交网络环境中将网络的最大度数都设定为40.实验中具体相关参数设置如下：

第1种社交网络环境中，全连通网络Agent集为21个，度数为20；小世界网络Agent集为100个，模拟真实的社交环境，最大度数限制为20，平均度数为8.8；随机树网络的Agent集为100个，模拟具有明显层次结构的环境，最大度数为20，平均度数为1.98.第2种社交网络环境中把全连通网络Agent集扩展到41，小世界网络和随机树网络的Agent集扩展为200，并限制最大度数为40.

单个Agent开销是0到1的随机分布；单个Agent的效用是开销的1.5倍到3倍；为了去除试验中随机过程的影响，每一次联通形成过程都将重复100次取置信度为95%的置信区间作为实验结果；为了得到SOCNCF机制那个的协作度信息，将进行10次联盟形成过程；初始协作度可以为15(激进型)、0.001(线性型)、-5(被动型)随机选择；为了既反映出Agent的协作态度，又反映出Agent的协作资源，协作度中取a,b都为0.5；同时为了使协作度对协商策略起到最为恰当的影响并且对邻居Agent协作度有较好的判断，β0设置为5，协商策略阀值Δcth为0.5.

5.2 实验结果分析

实验的第1部分是对比使用不同的社交网络时，SOCNCF机制和CFMSN机制在协商轮数上变化的差异性.实验的设置如5.1节描述所示，其中Agent网络环境设置为第1种，初始协作度是5.1节中所示的3种随机选择的.为了验证SOCNCF的有效性，将进行10联盟形成的过程，为了去除试验中随机因素的影响，每次联盟形成过程重复了100次取平均值.最终实验结果如图5所示.

方法

可以看出，全连通社交网络的协商次数在CFMSN机制中最少，但是它随着协作信息的累积没有很明显的减少联盟形成的协商次数；相反，小世界社交网络在CFMSN机制中联盟形成的协商次 数最大，但是由于SOCNCF机制中的协作度很好地反应了小世界社交网络的特性，使得它随着协作度信息的累集有很明显的协商次数改进，以至于到了SOCNCF-10时，它的协商次数最少.这反映了的SOCNCF机制更适合应用于小世界社交网络中，在不同的社交网络中具体的各项性能对比将在实验的第2部分进行.实验的第2部分是为了对比CFMSN机制和SOCNCF在不同网络拓扑结构中的性能，从而验证SOCNCF机制的有效性.实验中Agent社交网络环境分别取5.1节中所示的两种；Agent的初始协作度是实验1中3种协商策略随机选择的，SOCNCF机制的数据取的是第10次形成联盟时(SOCNCF-10)的数据；每次形成联盟时重复试验100次，取置信度为95%的置信区间作为结果.Agent网络环境为第1种时，实验结果如表1所示；Agent网络环境为第2种时，实验结果如表2所示.其中协商轮数是联盟形成中协商交互提议最多的次数；协商成功率是联盟形成后，Agent集中收敛的Agent占的比分比，联盟大小是形成的所有联盟的平均值；而平均个体效用是所有收敛的Agent获得的效用的平均值.

表1 第1种Agent社交网络环境下联盟形成效果对比

表2 第2种Agent社交网络环境下联盟形成效果对比

由表1可以看出，当使用第1种Agent网络环境时，由于SOCNCF机制使用了基于协作度的协商策略，能够动态改变给对手的协商态度值，使得该机制与单纯的基于网络的CFMSN机制相比具有更好的性能；同时虽然使用CFMS机制时小世界社交网络中的效果不是最好，但是由于SOCNCF机制中的协作度是Agent的协作资源和Agent的协作态度的综合反映，而小世界网络的高聚集性正好使得不同Agent之间的协作资源差异性较大，小世界网络的低平均路径使得Agent之间的协商成功率高，从而协商态度较好，所以SOCNCF机制在小世界社交网络中具有比其他两种社交网络更好的性能.

表2中采取的是第2种Agent社交网络环境，这时Agent的规模扩大，节点最大的度数也增加了.实验结果表明，本文机制对网络环境做出了变换时总体的趋势和表1是相同的，即SOCNCF机制性能比CFMSN机制好，同时采取SOCNCF机制形成联盟时小世界社交网络中的性能最好.这说明SOCNCF机制的性能不会因为Agent社交网络环境的变化而失效，适应于不同Agent大小、不同平均度数的Agent社交网络.

综合上面两部分实验可知，在CFMSN机制中，小世界社交网络与其他两种社交网络相比在联盟形成效率上不是最好的.但是SOCNCF机制通过引入协作度的概念，充分反映了小世界网络高聚集、低平均路径的特性，通过对协作度信息的累计后的SOCNCF在小世界网络中具有最好的联盟形成性能.而恰恰我们现实应用中的多Agent系统大多都是小世界社交网络，也就是说我们的SOCNCF机制具有很好的实用性.

6 总 结

本文提出的SOCNCF机制通过社交网络模拟实际应用中的多Agent环境，制约潜在的提议数；然后结合一系列的协商要素建立分布式协商协议，保证了该机制的收敛性；最后使用基于协作度的协商策略，既能提高联盟形成的效率又能反应不同的社交网络的差异性；最后通过实验分析验证了该机制的可行性和有效性，并且验证SOCNCF机制在小世界网络中的性能更突出，从而验证了SOCNCF的实用性.

[1] RAHWAN T, MICHALAK T, WOOLDRIDGE M,etal. Anytime coalition structure generation in multi-agent systems with positive or negative externalities[J]. Artificial Intelligence, 2012, 186: 95-122.

[2] 李少芳, 胡山立, 石纯一. 一种基于势结构分组思想的任一时间联盟结构生成[J]. 计算机研究与发展, 2012, 48(11): 2047-2054.

LI Shao-fang, HU Shan-li, SHI Chun-yi. An anytime coalition structure generation based on the grouping idea of cardinality structure[J]. Journal of Computer Research and Development, 2012, 48(11): 2047-2054. (In Chinese)

[3] 刘惊雷, 张伟, 童向荣, 等. 一种O(2.983n)时间复杂度的最优联盟结构生成算法[J]. 软件学报, 2011, 22(5): 938-950.

LIU Jing-lei, ZHANG Wei, TONG Xiang-rong,etal. O(2.983n) time complexity algorithm for optimal coalition structure generation [J]. Journal of Software, 2011, 22(5): 938-950.(In Chinese)

[4] SANDHOLM T. Agents in electronic commerce: Component technologies for automated negotiation and coalition formation[J]. Autonomous Agents and Multi-Agent Systems, 2000, 3(1): 73-96.

[5] VOICE T, RAMCHURN S D, JENNINGS N R. On coalition formation with sparse synergies[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems．New York:ACM,2012: 223-230.

[6] LIEMHETCHARAT S, VELOSO M. Modeling and learning synergy for team formation with heterogeneous agents[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems．New York:ACM, 2012: 365-374.

[7] SOH L，TSATSOULIS C. Allocation algorithms in dynamic negotiation-based coalition formation[C]//Proc of the 1st Int Conf on Autonomous Agents and Multiagent Systems. New York:ACM, 2002：16-23.

[8] SOH L K.Negotiation-based coalition formation model for agents with incomplete information and time constraints[R]. Lincoln, USA:Department of Computer Science and Engineering, University of Nebraska-Lincoln, 2002.

[9] 胡军, 邓磊, 宋颖辉. 面向议题关联的双边多议题协商模型研究[J]. 湖南大学学报:自然科学版, 2011, 38(12)：66-71.

HU Jun, DENG Lei, SONG Ying-hui. Research on interdependence-oriented bilateral multi-issue negotiation model[J]. Journal of Hunan University :Natural Sciences, 2011, 38(12)：66-71. (In Chinese)

[10]RAMCHURN Sarvapali D,GERDING Enrico,JENNINGS N R,etal.Practical distributed coalition formation via heuristic negotiation in social networks[C]//Fifth International Workshop on Optimisation in Multi-agent Systems(OPTMAS).Valencia ES,2012:205.

[11]汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京:清华大学出版社, 2006:5-22.

WANG Xiao-fan, LI Xiang, CHEN Guan-rong. Theory and application of the complex network[M]. Beijing:Tsinghua Unversity Press, 2006:5-22.(In Chinese)

[12]ABRAHAM A, HASSANIEN A E, SNASEL V. Computational social network analysis: trends, tools and research advances[M].Berlin:Springer Press, 2009:205.

Social Networks Oriented Collaboration Degree Based Negotiation Coalition Formation Mechanism

HU Jun1,4†, ZHANG Zhen-xing1,2, ZOU Li1,3

(1.College of Computer Science and Electronic Engineering, Hunan Univ, Changsha, Hunan 410082,China；2. Guangxi Key Laboratory of Trusted Software, Guilin Univ of Electronic Technology, Guilin, Guangxi 541004,China；3.State Key Laboratory for Novel Software Technology, Nanjing Univ, Nanjing, Jiangsu 210093,China；4. Key Laboratory for Embedded and Network Computing of Hunan Province,Huna Univ, Changsha, Hunan 410082,China)

The social networks formed by distributed multi-Agent always show different characteristics. This paper proposed a social networks oriented collaboration degree based negotiation coalition formation mechanism aiming at the heterogeneity of different social networks and multi-Agent. This mechanism established a distributed negotiation protocol and designed a collaboration degree based negotiation tactic, which considered the characteristics of the social networks and the heterogeneity of the Agent. The experiment results in fully-connected network, hierarchical network and small world network have shown that this mechanism can form coalition in distributed environment effectively and show a better performance than other social networks in responding to small world networks in practical environment.

multi Agent systems; coalition formation; distributed auto-negotiation; social networking; collaboration degree

1674-2974(2015)02-0100-09

2014-01-16

国家自然科学基金资助项目(60773208),National Natural Science Foundation of China(60773208); 湖南省自然科学基金资助项目(11JJ3065); 广西可信软件重点实验室研究资助项目(kx201333);计算机软件新技术国家重点实验室研究资助项目( KFKT2013B14)

胡 军(1971-)，男，湖南长沙人，湖南大学副教授，博士†通讯联系人，E-mail:hujun_111@hnu.edu.cn

TP311

A