正关系与负关系网络科学与策略机制市公开课金奖市赛课一等奖课件

15正关系与负关系PositiveandNegativeRelationships第1页Outline结构平衡(StructureBalance)边正负性三角关系中平衡关系和不平衡关系完全图结构平衡结构平衡定理弱结构平衡(WeaklyBalancedNetworks)结构平衡推广非完全图中结构平衡近似平衡网络2第2页边正负性社会网络中，两个节点之间关系（边）可能携带着各种各样社会性含义除了强弱以外，还有支持（＋）与反对（－），朋友（＋）与敌人（－）等利害关系3人和人之间如此，国和国之间外交关系也如此，而且后者经常显现得愈加显著（同盟条约、领土争端之类）第3页三角关系中结构平衡问题从社会心理学角度看，一个平衡三角关系要么（＋＋＋），要么（－－＋）。不然结构不平衡，即隐含有一个改变力量（趋势）4平衡平衡不平衡不平衡第4页中、朝、韩关系7月8日凤凰卫视节目中，韩国一个国际关系学者指出每当中国和韩国关系好时候，南北关系也就趋好，中韩关系不好时候，南北关系也就不好5＋＋中中朝朝韩韩＋＋－－第5页钓鱼岛问题中关系6－＋中国大陆中日日本中国台湾美－－？？第6页社会网络（图）结构平衡定义：（完全）图结构是平衡，若其中全部三角关系都是平衡（即每个三角关系要么3＋，要么1＋和2－）7第7页钓鱼岛问题中关系8＋－－？？？中国大陆中国台湾美国日本第8页平衡定理假如一个标识（＋／－）完全图是平衡则要么它全部节点两两都是朋友要么它节点能够被分为两组，X和Y，其中X组内节点两两都是‘＋’关系，Y组内节点两两也都是‘＋’关系，而X组中每个节点与Y组中每个节点之间都是‘－’关系9第9页平衡定理证实满足前述划分性质图符合平衡定义符合平衡定义图一定满足前述性质10＋＋＋＋－－从局部性质到全局状态第一点显然，此图用于说明第二点第10页平衡定理在国际关系分析中应用11奥地利与俄国也就不能稳定促成新联盟第11页弱平衡网络注意到在平衡网络中排除两种三角关系在社会关系含义（分量）上是有区分改变（－、－、－）动力弱一些改变（＋、＋、－）动力强一些弱平衡网络：只是不存在（＋、＋、－）三角关系标注完全图即：放松了对平衡要求弱平衡网络，也有类似于平衡定理性质12节点可分成若干组，组内均为朋友（＋），组间均为敌人（－）第12页13－＋“平衡”意味着改变关系属性动力不足，或者有较强维持现相关系性质动机集合内全部些人均互为朋友不一样集合间均互为敌人第13页弱平衡性质证实从一个节点开始，一个个“剥离”满足要求节点组图中考虑任意节点A，将它朋友和敌人分开，考查朋友组内与跨组边性质，暂时不论敌人组内边性质14－＋＋不存在第14页推广之一：非完全网络中结构平衡推广关键点：允许有些边缺失表示对应两个节点之间关系不存在或不清楚此时结构平衡定义能够经过补充缺失边（带符号），形成一个平衡网络和完全图平衡定义一致节点能够分成两组（组内边为＋，跨组为－）和平衡定理中给出宏观结论一致（两个阵营）这两个定义等价性？15第15页非完全图平衡定义等价性看一个简单例子16普通情况怎样？A：能够添加边形成平衡完全图B：能够分成两个敌对阵营假如能够经过添加边成平衡完全图（A），则能够分成两个阵营，去掉其中添加边，就是B填补成完全图将节点分成集合X和Y，集合内全部边为+，集合之间全部边为－第16页推广之一（续）定义B相对惯用，但依然不理想有没有简单判别法？17是否平衡？一个标识了正负关系非完全网络图第17页简单判别：启发假如存在一个含有奇数个“－”圈，就没有可能将其节点安排到两个敌对阵营从任何一个节点出发，碰到“＋”，必须保持阵营，碰到“－”必须换一个阵营，回到出发点时发觉矛盾18不过，普通来说发觉是否有那样圈也不轻易！第18页其中有没有奇数个“－”圈？认识：假如一个图节点能被分成两个阵营，则其中由“＋”互联连通子图必定完整地属于同一个阵营19这暗示：我们能够将那样子图作为一个整体考虑第19页识别以正边为基础连通子图以“+”互联连通子图看成一个超节点/团点(blobs)“超节点”之间只有“－”边形成简约图20超节点原图简约图第20页深入抽象原图中存在有奇数个“－”圈，当且仅当这个简约图中存在有奇数个“－”圈21第21页怎样确定图中是否有长度为奇数圈一个图是二部图，当且仅当它不存在包含有奇数个“－”圈22怎样有效判定一个图是否二部图？利用广度优先搜索(BFS)结果？第22页从任何一个节点开始做BFS图中存在包含有奇数个“－”圈，当且仅当广度优先搜索结果中存在同层边23以G点开始做BFS同层边不平衡第23页推广之二：近似平衡网络平衡定理条件极端，假如大多数三角形是平衡呢？放宽条件：24断言：设定ε为任意数，范围0≤ε≤1/8，定义。若在完全标注图中最少有1-ε占比三角形是平衡，则(1)最少存在1-δ占比节点，其中最少1-δ占比节点对都是互为朋友，或者(2)能够将节点划分成两个集合X和Y，满足●集合X中最少1-δ占比节点对都是互为朋友●集合Y中最少1-δ占比节点对都是互为朋友●在集合X和Y之间全部节点对中，最少1-δ占比节点对互为敌人注意：平衡定理就是ε=0时情形第24页25关键点结构平衡(St