An energy model for visual graph clustering

Abstract. We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the bestknown force and energy mo

AnEnergyModelforVisualGraphClustering

AndreasNoack

InstituteofComputerScience

BrandenburgTechnicalUniversityatCottbus

POBox101344,03013Cottbus,Germany

an@informatik.tu-cottbus.de

Abstract.Weintroduceanenergymodelwhoseminimumenergydrawingsre-vealtheclustersofthedrawngraph.Hereaclusterisasetofnodeswithmanyinternaledgesandfewedgestonodesoutsidetheset.Thedrawingsofthebest-knownforceandenergymodelsdonotclearlyshowclustersforgraphswhosediameterissmallrelativetothenumberofnodes.Weformallycharacterizetheminimumenergydrawingsofourenergymodel.Thischaracterizationshowsinwhatsensethedrawingsseparateclusters,andhowthedistanceofseparatedclus-terstotheothernodescanbeinterpreted.

1Introduction

Force-directedandenergy-basedmethodsarepopularforcreatingstraight-linedraw-ingsofundirectedgraphs.Theyarecomparativelyeasytoimplement,adapt-abletodifferentdrawingcriteria,andgivesatisfactoryresultsformanygraphs([4,Chap.10],[7]).Sincetheintroductionofmulti-scalealgorithmstheyareevenquiteef cient[28,15,17,26,29].

Energy-basedmethodsgenerallyhavetwoparts:anenergymodel,http://doc.guandang.netrce-directedmethods,themodelisaforcesystem,andanalgorithmsearchesforanequilibriumstatewherethetotalforceoneachnodeiszero.Becauseforceisthenegativegradientofenergy,thiscorre-spondstosearchingalocalminimumofenergy.Wewilltaketheperspectiveofenergyminimizationinthispaper.

Findingclusters,i.e.subsetsofnodeswithmanyinternaledgesandfewedgestooutsidenodes,ingraphsisanimportantprobleminVLSIdesign[2],parallelcomput-ing[25],softwareengineering[23],andgraphdrawing[9].Themostpopularforceandenergymodelsdonotclearlyisolateclusters,especiallyingraphswithsmalldiameter.The rstmainresultofthispaperisanenergymodelwhoseminimumenergydrawingsrevealtheclustersofsuchgraphs.

Thepurposeofenergymodelsistocreatedrawingsfromwhichahumanviewercaninferpropertiesofthedrawngraph.Tomaketheinferencemoreef cientanditsresultsmorevalid,thedrawingsarerequiredtohavecertainproperties,likesmallanduni-formedgelengths,well-distributednodes,orwell-separatedclusters.Empiricalstudieswereperformedtoevaluatetowhatdegreeforceandenergymodelsful llsuchcriteria(e.g.[6]),butfewanalyticalresultsexist.Aformalcharacterizationoftheminimumenergydrawingsofourenergymodelisthesecondmainresultofthispaper.

Abstract. We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the bestknown force and energy mo

ThenewenergymodelanditsformalanalysisarepresentedinSect.2.Sec-tion3showsexampledrawingsandcomparesthemwithdrawingsofthewell-knownFruchterman-Reingoldforcemodel[14].Section4comparesourenergymodelwithexistingforceandenergymodels,andproposesageneralizationthatincludesamongothersourenergymodelandtheFruchterman-Reingoldmodel.Itdiscussesapplica-tions,theimportanceofinterpretability,andthebene tsoftheoreticalanalysesofen-ergymodels.

1.1BasicDe nitions

AgraphG=(V,E)consistsofa nitesetVofnodesanda nitesetEofedgeswithE V(2),whereV(2)isthesetofallsubsetsofVwhichhaveexactlytwoelements.Weonlyconsidergraphswithatleasttwonodes.Becauselayoutscanbecomputedsep-aratelyfordifferentcomponentsofagraph,werestrictourselvestoconnectedgraphs,i.e.graphswhereeverypairofnodesisconnectedbyapath.

Fortwonodesu,v∈V,thelengthoftheshortestpathconnectinguandvisthegraph-theoreticdistanceofuandv.ThediameterofthegraphGisthegreatestgraph-theoreticdistancebetweenanytwonodes.AcutofGisapair(V1,V2)ofnonempty,disjointsetsofnodeswithV1∪V2=V.

ForV1,V2 VandF V(2)letF[V1]={{u,v}∈F|u,v∈V1}andF[V1,V2]={{u,v}∈F|u∈V1,v∈V2}.ThenE[V1]isthesetofedgesinV1,andE[V1,V2]isthesetofedgesbetweenV1andV2.

Ad-dimensionaldrawingofthegraphGisavectorp=(pv)v∈Vofnodepositionspv∈IRd.Foradrawingpandtwonodesu,v∈Vthelengthofthedifferencevectorpv puiscalledthe(Euclidean)distanceofuandvinpanddenotedby||pv pu||.ForasubsetFofV(2)andadrawingp,thearithmeticmeanarithmean(F,p)ofthedistancesofFisde nedas

1 ||pv pu||,arithmean(F,p)={u,v}∈F|F|

thegeometricmeangeomean(F,p)ofthedistancesofFisde nedas geomean(F,p)=|F|||pv pu||,{u,v}∈F

andtheharmonicmeanharmmean(F,p)ofthedistancesofFisde nedas

harmmean(F,p)=|F|

{u,v}∈Fvu.

2LinLog:AClusteringEnergyModel

Inthissection,we rstde neanewenergymodel,calledLinLog,http://doc.guandang.netingthismeasurewecanformalizeandprovethatinminimumenergydrawingsoftheLinLogmodel,clustersareclearlyseparatedfromtheremaininggraph,andthedistanceofeachclustertotheremaininggraphisinterpretablewithrespecttopropertiesofthegraph(moreprecisely,thedistanceisapproximatelyinverselyproportionaltothecoupling).

Abstract. We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the bestknown force and energy mo

2.1TheLinLogEnergyModel

{u,v}∈ETheLinLogenergyULinLog(p)ofadrawingpisde nedasULinLog(p)=||pu pv||

{u,v}∈V(2)ln||pu pv||

The rsttermofthedifferencecanbeinterpretedasattractionbetweenadjacentnodes,andthesecondtermcanbeinterpretedasrepulsionbetweenanytwo(different)nodes.Toavoidin niteenergiesweassumethatdifferentnodeshavedifferentpositions.Thisisnoseriousrestrictionbecauseweareinterestedingooddrawings,i.e.drawingswithlowenergy.

2.2TheCutRatioasaMeasureofCoupling

Manydifferentde http://doc.guandang.netr-mally,wedenotebyclusterasetofnodeswithmanyinternaledges(highcohesion)andfewedgestonodesoutsidetheset(lowcoupling).Similarde nitionsareusedinVLSIdesign[2],paral …… 此处隐藏：27491字，全部文档内容请下载后查看。喜欢就下载吧 ……