结构平衡与人际评价动力学-SIH-SIOH八卦模型

结构平衡与人际评价动力学：SIH/SIOH八卦模型StructuralBalanceandInterpersonalAppraisalDynamics作者：WenjunMei、GeChen、NoahE.Friedkin、FlorianDörfler【内容简介】研究非全连接网络中结构平衡如何通过局部人际评价动力学涌现，提出SIH和SIOH两种评价动力学模型。当个体仅根据邻居关系调整态度时，网络能否达到全局结构平衡？研究发现SIH模型总是收敛于结构平衡状态，而SIOH模型收敛于一个近平衡的稳定态。适用于社会网络分析、舆论传播、复杂网络动力学等领域。【关键词】结构平衡理论、社会网络、人际评价、八卦动力学、同质机制、社会影响力、复杂网络【来源】arXiv:2012.10151v2——————————————————————————————StructuralBalanceandInterpersonalAppraisalsDynamics:BeyondAll-to-AllandTwo-FactionNetworksWenjunMeia,GeChenb,NoahE.Friedkinc,FlorianD¨orfleraaAutomaticControlLaboratory,ETHZurich,SwitzerlandbAcademyofMathematicsandSystemsScience,ChineseAcademyofSciences,Beijing,ChinacDepartmentofSociology,UniversityofCalifornia,SantaBarbaraAbstractStructuralbalancetheorydescribesstableconfigurationsoftopologiesofsignedinterpersonalappraisalnetworks.Existingmodelsexplainingtheconvergenceofappraisalnetworkstostructuralbalanceeitherdivergeinfinitetime,orcouldgetstuckinjammedstates,orconvergetoonlycompletegraphs.Inthispaperwestudytheopenproblemhowsteadynon-all-to-allstructuralbalanceemergesvialocaldynamicsofinterpersonalappraisals.Wefirstcomparetwowell-justifieddefinitionsofstructuralbalanceforgeneralnon-all-to-allgraphs,i.e.,thetriad-wisestructuralbalanceandthetwo-factionstructuralbalance,andthoroughlystudytheirrelations.Secondly,basedonthreewidelyadoptedsociologicalmechanisms:thesymmetrymechanism,theinfluencemechanism,andthehomophilymechanism,weproposetwosimplemodelsofgossip-likeappraisaldynamics,thesymmetry-influence-homophily(SIH)dynamicsandthesymmetry-influence-opinion-homophily(SIOH)dynamics.Inthesemodels,theappraisalnetworkstartingfromanyinitialconditionalmostsurelyachievesnon-all-to-alltriad-wiseandtwo-factionstructuralbalanceinfinitetimerespectively.Moreover,theSIOHdynamicscapturetheco-evolutionofinterpersonalappraisalsandindividuals’opinions.Regardingthetheoreticalcontributions,weshowthattheequilibriumsetoftheSIH(SIOHresp.)dynamicscorrespondstothesetofallthepossibletriad-wise(two-factionresp.)structuralbalanceconfigurationsoftheappraisalnetworks.Moreover,weprovethat,foranyinitialcondition,theappraisalnetworksintheSIH(SIOHresp.)dynamicsalmostsurelyachievetriad-wise(two-factionresp.)structuralbalanceinfinitetime.NumericalstudiesoftheSIHdynamicsareconductedonhowthefinalproportionofnegativelinksdependsontheinitialproportionofnegativelinksandthenetworktopology.Thesesimulationresultsimplysomeinsightfultake-homemessagesonwhethermultilateralrelationsreduceorexacerbateconflicts.Keywords:Structuralbalance;Signedsocialnetworks;Co-evolutionarydynamics;Influenceprocess;Homophily.1IntroductionMotivationandproblemdescriptionPropertiesanddynamicson/ofsignednetworkshavebeenwidelystudiedinsocialscienceaswellasappliedmathematics.Structuralbalance(alsoreferredtoassocialbalance)the-ory,firstproposedintheseminalworksbyHeider[17,18],characterizesthestableconfigurationsofinterpersonalappraisalnetworkswithbothfriendlyandantagonisticrelations.Anappraisalnetworksatisfiesstructuralbal-anceifeachindividualobeysthefamousHeider’sax-ioms:Friends’friendsarefriends;Friends’enemiesareenemies;Enemies’friendsareenemies;Enemiesenemies‹ThismaterialisbaseduponworksupportedinpartbytheETHZurichfunding.Emailaddresses:wmei@ethz.ch(WenjunMei),chenge@(GeChen),friedkin@(NoahE.Friedkin),dorfler@ethz.ch(FlorianD¨orfler).arefriends.”Assuggestedby[17,18],imbalanceofin-terpersonalrelationssensedbyindividualsleadstocog-nitivedissonancesthattheindividualsstrivetoresolve.Dynamicstructuralbalancetheory,aimingtoexplainhowaninitiallyunbalancednetworkevolvestoabal-ancedstate,hasrecentlyattractedmuchinterest.Inex-istingmodels[2,3,30,23,20,24,29,31,26],appraisalnet-workseitherdivergeinfinitetime,orgetstuckinunbal-ancedequilibria,orconvergetoall-to-allgraphssatisfy-ingstructuralbalance.Itremainsanopenproblemwhatmodelsleadtotheconvergenceofappraisalnetworkstostructuralbalancewitharbitrarynon-all-to-allnetworktopologies.Inthispaper,weaddressthisopenproblem.Tobemorespecific,weproposeandanalyzedynamicsofinterpersonalappraisalsinwhichtheappraisalnetworksareinitiallynon-all-to-allandconvergetostructurallybalancedequilibriawithalsoanon-all-to-alltopology.Beforestudyingtheconvergenceofinterpersonalap-PreprintsubmittedtoAutomatica24December2020arXiv:2012.10151v2[cs.SI]23Dec2020praisalstonon-all-to-allstructuralbalance,onewouldneedtofirstclarifywhatstructuralbalancemeansinthisscenario.Inthispaper,theinterpersonalappraisalnet-worksaremodeledassignedgraphs.Intuitively,struc-turalbalanceinnon-all-to-allsignedgraphscanbede-finedintwoways.Thefirstoneisastraightforwardgen-eralizationoftheaforementionedHeider’sfouraxioms.Mathematically,Heider’sfouraxiomsmeanthat,everythreenodes(i.e.individuals)intheappraisalnetworkforma“positivetriad”,i.e.,atriadwitheitherthreesymmetricpositiverelationsortwosymmetricpositiverelationsandonesymmetricnegativerelation.Sinceev-erythreenodesinanon-all-to-allgraphdonotneces-sarilyformatriad,anintuitivegeneralizationofHei-der’saxiomsistorequirethateveryexistingtriadintheappraisalnetworkispositive.Werefertosuchadefini-tionastriad-wisestructuralbalance.ComparedtoHei-der’sclassicstructuralbalance,triad-wisebalanceal-lowsformorerealisticscenarios,e.g.,onedoesnotnec-essarilyknowallofher/hisfriends’friends.Theseconddefinition,referredtoastwo-factionstructuralbalance,wasfirstproposedbyCartwrightetal.[7]andhasbeenwidelyadoptedinthestudiesofopiniondynamicsonsignednetworks[1,22,28].Itrequiresthattheappraisalnetworkcanbepartitionedintotwoantagonisticfactionswheretheinter-factionrelationsareallnon-positiveandtherelationswithineachfactionareallnon-negative.Inthispaper,wefirstthoroughlystudytherela-tionsbetweentriad-wisestructuralbalanceandtwo-factionstructuralbalance,andthenproposetwosimplediscrete-timedynamicmodels,thesymmetry-influence-homophily(SIH)modelandthesymmetry-influence-opinion-homophily(SIOH)model,suchthattheinter-personalappraisalsalmostsurelyconvergetotriad-wiseandtwo-factionnon-all-to-allstructuralbalancerespec-tively.Inourmodels,linksinappraisalnetworkstakevaluesfromt´1,1,0u,correspondingtoantagonistic,friendly,andno/neutralrelationsrespectively.Atanytime,onesuchlinkisactivatedandupdatedvia(someof)thefollowingsociologicalmechanismsoflocalin-teractions:thesymmetrymechanism[12],theinfluencemechanism[14],theperson-personhomophilymecha-nism[21],andtheperson-opinionhomophily[7].Thesymmetrymechanismmeansthatindividualstendtobefriendlyto(antagonisticagainstresp.)thosewhoarefriendlyto(antagonisticagainstresp.)themselves.Theinfluencemechanismassumesthatoneindividual’sattitudetowardsanotherisinfluencedbytheirmutualsocialneighbors’attitudes.Thehomophilymechanismsingeneralmeanthatindividualsarefriendlyto(an-tagonisticagainstresp.)eachotheriftheyholdsimilaropinionsonsomeissues,orsimilarappraisalsofothers.LiteraturereviewFollowingtheearlyworksbyHeider[17,18],staticstructuralbalancetheoryhasbeenextensivelystudied,includingthecharacteriza-tionofthebalancedconfigurations[7,11],thedegreeofbalance[6,19],andempiricalvalidations[25,27,13].GeneralizedstructuralbalancehasalsobeenstudiedintermsofremovingsomeofHeider’sfouraxioms,e.g.,see[10,4].Differentfromthesegeneralizations,thetriad-wisestructuralbalanceproposedinthispaperex-tendstheapplicabilityoftheclassicHeider’sstructurebalancefromall-to-allgraphstoarbitrarytopologiesbyrequiringalltheexistingtriadsintheappraisalnetworktosatisfyHeider’sfouraxioms.Foracomprehensivere-viewofstaticstructuralbalancetheory,wereferto[32].Previousworksondynamicstructuralbalancetheoryincludethediscrete-timelocaltriaddynamics(LTD)[2]andconstrainedtriaddynamics[3].Thesemodelssufferfromtheexistenceofunbalancedequilibria,i.e.,thejammedstates.OthermodelsbasedonnetworkgamesareproposedbyMalekzadehetal.[23]andvandeRijt[30].Themodelin[23]appliestoonlycompletegraphs.Themodelin[30]proposesmoothedbest-responsedynamicswithvanishingnoise,inwhichsomegeneralizedstructurallybalancedgraphswitharbitrarytopologiesaretheonlystochasticallystableconfigura-tions.Butstochasticstabilityisaweakerconditionthanalmost-sureconvergence,andthemodelin[30]actuallydoesnotadmitanysteadystate.Friedkinetal.[15]proposeageneralizedmodelbasedonruleoftransitiveclosureinwhichthetemporaleliminationofviolationsofHeider’sfouraxiomsappearsasaspecialcase.Dynamicstructuralbalancemodelswithcontinu-ouslinkweightshavealsobeenwidely-studied,e.g.,see[20,24,29,26,9].Intermsofthemicroscopicsocio-logicalmechanism,thesemodelsareallbasedoneithertheinfluencemechanism[14]orthehomophilymecha-nism[21].Inthesemodels,theappraisalnetworkseitherdivergeinfinitetime[20,24]orconvergefromcertainsetsofinitialconditionstocompletegraphssatisfyingstructuralbalance[26,9].ContributionsThecontributionsofthispaperareasfollows.Firstly,weconductcomprehensiveanalysisoftherelationbetweentriad-wisestructuralbalanceandtwo-factionstructuralbalancefornon-all-to-allappraisalnetworks.Weshowthatifadirectedsignedgraphsatisfiestriad-wisestructuralbalance,thenanynode’sego-networksatisfiestwo-factionstructuralbal-ance.Moreover,weprovideagraph-theoreticconditionwithcleargeometricinterpretation,underwhichthesetwodefinitionsofstructuralbalanceareequivalent.Secondly,tothebestofourknowledge,theSIHandSIOHmodelsproposedinthispaperarethefirsttoestablishthealmost-sureconvergenceofinterpersonalappraisals,vialocalsocialinteractions,totriad-wiseandtwo-factionnon-all-to-allstructuralbalancerespec-tively.Sincerealsocialnetworksareusuallynotall-to-all2graphs,ourmodelssignificantlybroadentheapplicabil-ityofthedynamicstructuralbalancetheoryand,inthissense,aremorerealisticthanpreviousmodels.Thirdly,regardingthetheoreticalanalysisoftheSIH(SIOHresp.)model,weprovethatitsequilibriumsetcorrespondstothesetofallthepossibletriad-wise(two-factionresp.)balancedconfigurations.Wefurthershowthat,foranyinitialcondition,theappraisalnetworkal-mostsurelyreachesatriad-wise(two-factionresp.)bal-ancedequilibriuminfinitetime.FortheSIOHdynamics,wealsoprovetheconvergenceofindividuals’opinions.Fourthly,bynumericalstudies,weinvestigatehowthefinaldegreeofconflictsoftheSIHdynamics,i.e.,thera-tioofnegativelinksatthefinalsteadystates,dependsontheinitialdegreeofconflictsandthenetworktopol-ogy.Simulationresultsleadtoveryclearandinsightfulsociologicalinterpretations:1)Thefinaldegreeofcon-flictstendtoincreasewiththeinitialdegreeofconflictsandsuchcorrelationisstrongerinsparsernetworks;2)Multilateralrelationstendtoreducethefinaldegreeofconflictswhentheinitialdegreeofconflictsishigh,buttendtoincreasethefinaldegreeofconflictswhentheinitialdegreeofconflictsislow.Inaddition,suchcorre-lationsarestrongerinsparsernetworks.OrganizationTherestofthispaperisorganizedasfollows.Section2isaboutsomebasicnotationsanddef-initions.Section3presentstheresultsontherelationbetweentriad-wisestructuralbalanceandtwo-factionstructuralbalance;InSection4,weproposeandana-lyzetheSIHandSIOHdynamicsrespectively.Section5presentsthenumericalstudyandsomefurtherdiscus-sions.AlltheproofsareprovidedintheAppendix.2NotationsandDefinitionsLetφbetheemptysetandNbethesetofnaturalnumbers.LetV“t1,2,...,nu.Twotypeofgraphsareinvolvedinthispaper.Adi-rectedandunweightedsignedgraphwithnnodesisde-notedbyáG“pV,áE`,áE´q,whereVisthenodessetandthetwodisjointsetsáE`ĎVˆVandáE´ĎVˆVarethesetofallthepositiveandnegativedirectedlinksináGrespectively.Weonlyconsiderunweightedgraphsandtherebytheterm“unweighted”isomittedintherestofthispaper.Anundirectedunsignedgraphisde-notedby|G|“pV,Eq,whereEisthesetofalltheundi-rectedlinks.Adirectedpath(pathresp.)ináG(|G|resp.)fromnodei1tonodeimisanorderedsequenceofnodesi1,...,imsuchthatpik,ik`1qPáE`YáE´(tik,ik`1uPEresp.)foranyk“1,...,m´1.Thisdirectedpath(pathresp.)haslengthm´1.AgrapháG(|G|resp.)isstronglyconnected(connectedresp.)if,foranyi,jPV,thereexistsatleastonedirectedpath(pathresp.)fromitoj.Anorderedsequencepi1,...,imqofnon-repeatingnodesisacyclewithlengthmináG(|G|resp.)ifpik,ik`1qPáE`YáE´(tik,ik`1uPEresp.)foranykPt1,...,mu.Herewetakeim`1asi1.AcycleonáGispositiveifitcontainseitherzerooranevennumberofnegativelinks.Atriadisacyclewithlength3andapairofnodeslinkingtoeachotherisacyclewithlength2.GivenagrapháG(|G|resp.)andasubsetofnodes˜VĎV,denotebyáG˜V(|G|˜Vresp.)theinducedsubgraphofáG(|G|resp.)associatedwith˜V.Namely,áG˜V“p˜V,áE`˜V,áE´˜Vq,whereáE`˜V“p˜Vˆ˜VqXáE`andáE´˜V“p˜Vˆ˜VqXáE´,and|G|˜V“p˜V,E˜Vq,whereE˜V“␣ti,juˇˇi,jP˜V(XE.Givenasubsetofnodes˜VĎVandsubsetsoflinks˜áE`ĎáE`˜Vand˜áE´ĎáE´˜V(˜EĎE˜Vresp.),thegraph˜áG“p˜V,˜áE`,˜áE´q(˜|G|“p˜V,˜Eqresp.)iscalledasubgraphofáG(|G|resp.)withthenodesset˜V.Givenagroupofnindividuals,theirinterpersonalap-praisalsarecharacterizedbyaternaryappraisalmatrixX“pXijqnˆnPt´1,0,1unˆn.HereXij“1(Xij“´1resp.)meansthatindividualiisfriendly(antagonisticresp.)toindividualj,whileXij“0meansthatei-theridoesnotknowjoriholdsneutralattitudeto-wardsj.AnappraisalmatrixXinducesadirectedandsignedgrapháGpXq“`V,áE`pXq,áE´pXq˘,referredtoastheappraisalnetwork,whereáE`pXq“tpi,jqPVˆV|Xij“1uandáE´pXq“tpi,jqPVˆV|Xij“´1u.ThematrixXalsoinducesanundirectedunsignedgraph|G|pXq“pV,EpXqq,whereEpXq“␣ti,ju|i,jPV,Xij‰0(.Inthispaper,weusetheterms“graph”and“network”interchangeably.TheappraisalsnetworkáGpXqisbilateral,or,equivalently,theappraisalmatrixXisbilateral,if“Xij‰0ôXji‰0”holdsforanyi,jPV.Weconsidernoselfloop,i.e.,Xii“0foranyiPV.ForanyXPt´1,0,1unˆn,define|G|pXq“pV,EqasV“t1,...,nuandE“␣ti,juˇˇXij‰0orXji‰0(.Thetriad-wisestructuralbalancedescribedintheIn-troductionismathematicallyformalizedasfollows.Definition2.1(Triad-wisestructuralbalance).Anap-praisalnetworkáGpXqsatisfiestriad-wisestructuralbal-ance,or,equivalently,istriad-wisebalanced,iftheap-praisalmatrixXsatisfiesthefollowingproperties:P1:(Symmetricappraisals)XijXjią0foranypi,jqPáE`YáE´;P2:(Positivetriads)XijXjkXkią0foranytriadpi,j,kqináGpXq.Notethat,bypropertyP1above,anyappraisalnet-worksatisfyingtriad-wisestructuralbalanceisbilateral.3Thetwo-factionstructuralbalanceisdefinedbelow.Definition2.2(Two-factionstructuralbalance).AnappraisalnetworkáGpXqsatisfiestwo-factionstructuralbalance,or,equivalently,istwo-factionbalanced,ifeitheráGpXqhasnonegativelinkoritsnodessetVcanbepartitionedintotwodisjointsetsV1andV2suchthatXijě0,foranyi,jPV1oranyi,jPV2,andXijď0,foranyiPV1,jPV2,oranyiPV2,jPV1.Thefollowinglemmawasfirstproposedin[7]andprovidesanecessaryandsufficientconditionfortwo-factionstructuralbalanceinstronglyconnectedgraphs.Lemma2.3(Cycle-wisestructuralbalance).GivenabilateralandstronglyconnectedappraisalnetworkáGpXq,itsatisfiestwo-factionstructuralbalanceifandonlyifeverycycleináGpXqispositive.3RelationsbetweenTriad-WiseStructuralBalanceandTwo-FactionStructuralBalance3.1GeneralrelationsTriad-wisestructuralbalanceisalocalfeatureofsignedappraisalnetworks,whiletwo-factionstructuralbalancecharacterizessomeglobalstructure.Itiswellknownthat,inall-to-allappraisalnetworks,thesetwodefinitionsareequivalent[7].Innon-all-to-allbilateralappraisalnetworks,wehavethefollowingobviousfact.Fact3.1.GivenabilateralappraisalmatrixXPt´1,0,1unˆn,theassociatedappraisalnetworkáGpXqsatisfiestriad-wisestructuralbalanceifáGpXqsatisfiestwo-factionstructuralbalance.Ingeneral,triad-wisestructuralbalancedoesnotim-plytwo-factionstructuralbalance,e.g.,seeFigure1.However,somemeaningfulconnectionscanstillbemadefromtriad-wisestructuralbalancetotwo-factionstruc-turalbalance.ForanyiPVináGpXq,defineNi“tjPV|Xij‰0uYtiuanddefinetheinducedsubgrapháGNipXqasnodei’sego-network,i.e.,theinducedsub-graphináGpXqinvolvingnodeiitselfandallthenodesthatnodeihaslinksto.Wehavethefollowingproposi-tionanditsproofisgiveninAppendixA.Proposition3.2(Structuralbalanceinego-networks).ForanyappraisalmatrixXPt´1,0,1unˆn,ifáGpXqsatisfiestriad-wisestructuralbalance,thenáGNipXqsat-isfiestwo-factionstructuralbalanceforanyiPV.Proposition3.2hasaclearsociologicalinterpretation.Sinceindividualsstrivetoresolvethecognitivedisso-nancegeneratedfromstructuralimbalanced[17,18]andsince,intuitively,individualscanfeeltheimbalancefromonlytheirego-networks,aslongastheentireappraisalnetworksatisfiestriad-wisebalance,alltheindividuals’ego-networkssatisfystructuralbalanceinboththetriad-wisesenseandthetwo-factionsense.Therefore,when-everanappraisalnetworksatisfiestriad-wisestructural(a)Graph1(b)Graph2Fig.1.Examplesofthedifferencebetweentriad-wisestruc-turalbalanceandtwo-factionstructuralbalance.Hereallthedirectedlinksarebilateralandsign-symmetric.Thereforethearrowsareomitted.Solidlinesmeanpositivebilaterallinkswhiledashlinesmeannegativebilaterallinks.Graph1satisfiesbothdefinitionsofstructuralbalance.Graph2sat-isfiestriad-wisestructuralbalancebutdoesnotsatisfytwo–factionstructuralbalance.However,foreachnodeinGraph2,herego-networksatisfiestwo-factionstructuralbalance.balance,evenifitisnottwo-factionbalanced,individu-alsshouldnotfeelanycognitivedissonanceandtherebyhavenomotivationtofurtheradjusttheirappraisalsofothers.InSection4,wewillseeaprofoundimplicationofProposition3.2:anysortoflocalappraisaldynamicsdrivenbyimbalanceinindividuals’ego-networksdonotnecessarilyachievetheglobaltwo-factionbalance.3.2ConditionsforequivalenceInthissubsection,wefurtherinvestigateunderwhatconditionsthetriad-wisestructuralbalanceisequiva-lenttothetwo-factionstructuralbalanceinnon-all-to-allappraisalnetworks.ThemainresultsreplyonsomeimportantconceptsandpropertiespresentedbelowbyDefinitions3.3,3.4,3.7,Facts3.5,3.8,andLemma3.6.SeeFigure2fortheirvisualizedillustrations.Definition3.3(Maximalcyclicsubgraph).Consideranundirectedunsignedgraph|G|“pV,Eq.Aninducedsubgraph|G|˜Vwith˜VĎVisamaximalcyclicsubgraphifitsatisfiesthefollowingtwoconditions:(i)Thereexistsacyclepi1,...,imqin|G|pass-ingthroughexactlyallthenodesin˜V,i.e.,˜V“ti1,...,imu;(ii)ForanyˆVsuchthat˜VĂˆV,theredoesnotexistacyclein|G|thatpassesthroughallthenodesinˆV,i.e.,thenodesi1,...,imarenotinanycyclelongerthanpi1,...,imqin|G|.Definition3.4(Chordsandchordalgraphs[5]).Inundirectedunsignedgraphs,alinkisachordofacycleifitconnectstwonon-consecutivenodesonthatcycle.Anundirectedunsignedgraphisachordalgraphifeverycy-clewithlengthgreaterthanthreehasatleastonechord.Atriadaloneisalsoachordalgraph.Regardingcyclesandchords,thefollowingisobvious.Fact3.5.Givenacyclepi1,i2...,imqinanundirectedunsignedgraph|G|“pV,Eq,iftip,iquPEisachordofthiscycle,withqąp`1,thenpi1,...,ip,iq,imqandpip,ip`1,...,iqqarebothcyclesingraph|G|.Thefollowinglemmaaboutchordalgraphsarefre-quentlyusedinthispaper.441235671234567Graph1Graph2Fig.2.Visualizedillustrationsofmaximalcyclicsubgraphs,chordalgraphs,andsubchordalcycles.DenoteGraph1(undirectedandunsigned)by|G|.Theinducedsubgraph|G|t3,4,5,6,7uisamaximalcyclicsubgraph,whiletheinducedsubgraph|G|t3,4,5,6uisnot.Thelinkst3,6u,t3,5u,andt5,7uarechordsofthecyclep3,4,5,6,7q.AsindicatedbyFact3.5,t3,6usplitsthecyclep3,4,5,6,7qintotwocyclesp3,6,7qandp3,4,5,6q.Graph1isachordalgraphaccordingtoDefini-tion3.4,andonecouldeasilycheckthatanyofitsinducedsubgraphsisalsochordal,asindicatedbyLemma3.6.Graph2isnotachordalgraphsincesomeofthecycleswithlengthgreaterthan3,e.g.,p3,4,5,6q,doesnothaveachord.How-ever,thecyclep3,4,5,6,7qinGraph2isasubchordalgraphsincethesubgraph|G|1“pV1,E1q,withV1“t3,4,5,6,7uandE1“␣t3,4u,t4,5u,t5,6u,t6,7u,t7,3u,t4,7u,t5,7u(isachordalgraph.AsindicatedbyFact3.8,ifp3,4,5,6,7qinGraph2isembeddedonaplaneasaconvexpolygon,thenthereexisttriadsp3,4,7q,p4,5,7q,andp5,6,7qin|G|1corre-spondingtoanon-overlappingpartitionofthispolygon.Lemma3.6(Inducedchordalsubgraphs[5]).Everyin-ducedsubgraphofachordalgraphisalsochordal.Definition3.7(Subchordalcycles).Acyclepi1,...,imqinanundirectedunsignedgraph|G|“pV,Eqisasubchordalcycleifin|G|thereexistsasubgraph|G|1“pV1,E1qassociatedwithCsuchthat(i)V1“ti1,...,imu,i.e.,thenodesetof|G|1isthesetofallthenodesinthecycle;(ii)␣ti1,i2u,ti2,i3u,...,tim,i1u(ĎE1,i.e.,|G|1con-tainsallthelinksthecycle;(iii)|G|1isachordalgraph.Theconceptofsubchordalcycleshasaveryclearge-ometricinterpretationandtheproofisinAppendixB.Fact3.8.Supposeacyclepi1,...,imqinanundirectedunsignedgraph|G|isasubchordalcycle,associatedwithasubgraph|G|1asdefinedinDefinition3.7.If|G|1isembeddedonaplanesuchthatthecyclepi1,...,imqformsaconvexpolygon,thenthereexistsasetoftriadsin|G|1,i.e.,trianglesontheplane,thatformsanon-overlappingpartitionofthepolygon.Withallthepreparationwork,nowwearereadytopresentsomegraph-theoreticconditionsonwhichthetriad-wisestructuralbalanceandthetwo-factionstruc-turalbalanceareequivalent.Firstofall,wepointoutthat,asastraightforwardconsequenceofstatement(iii)ofLemmaC.1andLemma2.3,thetriad-wisestructuralbalanceandthetwo-factionstructuralbalanceareequiv-alentifthecorrespondingundirectedunsignedgraphisconnectedandeverycycleinitissubchordal.Proposition3.9.Givenanyundirectedunsignedgraph|G|thatisconnected.Ifeverycycleinitissubchordal,12345(b)Graph21234567(c)Graph3123456(d)Graph412345(a)Graph16Fig.3.Exampleswheretriad-wisestructuralbalanceisorisnotequivalenttotwo-factionstructuralbalance.Inallthesedirectedsignedgraphsthelinksarebilateralandsign-sym-metric,andthearrowsoflinksaretherebyomitted.Solidlinesrepresentpositivebilaterallinkswhiledashedlinesrep-resentnegativebilaterallinks.Inpanel(a),thecorrespond-ingundirectedunsignedgraphsatisfiestehconditionsinProposition3.9.Inpanel(b),thecorrespondingundirectedunsignedgraphsatisfiesalltheconditionsinTheorem3.10,butdoesnotsatisfiestheconditonsinPropisition3.9sincethecyclep1,3,4,5qisnotsubchordal.Graph1andGraph2areexampleswherethedirectedsignedappraisalnetworkssatisfybothtriad-wiseandtwo-factionstructuralbalance.Thegreynodesformonefactionandtheothernodesforman-otherfaction.Inpanel(c),thecorrespondingundirectedun-signedgraph|G|itselfismaximalcyclicbutnotsubchordal.Asaresult,Graph3satisfiestriad-wisestructuralbalancebutitsnodescannotbepartitionedintotwofactions.Inpanel(d),thecyclep1,2,...,6qinthecorrespondingundi-rectedunsignedgraphissubchordalbutthelinkt1,4uvio-latesconditionii)inTheorem3.10.Asaresult,Graph4istriad-wisebalancedbutnottwo-factionbalanced.then,foranybilateralappraisalnetworkáGpXqwith|G|pXq“|G|,áGpXqsatisfiestriad-wisestructuralbal-anceifandonlyifáGpXqsatisfiestwo-factionbalance.Theconditionfortheequivalencebetweentriad-wiseandtwo-factionbalancecanbefurtherrelaxed.BelowwepresentthemaintheoremofthissectionanditsproofisprovidedinAppendixC.Theorem3.10(Equivalencebetweentwodefinitionsofstructuralbalance).Consideranyundirectedunsignedgraph|G|“pV,Eqthatisconnectedandsatisfiesthefollowingconditions:Foranymaximalcyclicsubgraph|G|1withmą3nodes,(i)itcontainsacycleC“pi1,...,imqthatpassesthroughallthenodesin|G|1andissubchordal;(ii)foranychordtip,iquofCin|G|,withqąp`1,atleastoneofthetwocyclespi1,...,ip,iq,...,imqandpip,ip`1,...,iqqin|G|issubchordal.ForanybilateralXPt´1,0,1unˆnwith|G|pXq“|G|,áGpXqsatisfiestriad-wisestructuralbalanceifandonlyifáGpXqsatisfiestwo-factionstructuralbalance.InFigure3weprovideexamplesinwhichtheundi-rectedunsignedgraphs|G|satisfy(ornotresp.)thecon-ditionsinTheorem3.10and,astheconsequences,triad-wisebalanceinanyáGpXqwith|G|pXq“|G|always(ornotresp.)alwaysimpliestwo-factionbalance.54ConvergenceofAppraisalNetworkstoNon-All-to-AllStructuralBalance4.1Convergencetotriad-wisestructuralbalanceInthissubsectionweproposeandanalyzeadiscrete-timegossip-likemodelthatcharacterizeshowappraisalnetworksevolvestotriad-wisestructuralbalancewithnon-all-to-alltopologiesvialocalinteractions.Thismodelisbuiltonthreesociologicallyintuitivemecha-