surveygraphcore

FindingDenseSubgraphswithSizeBoundsReidAndersenandKumarChellapillaMicrosoftLiveLabs,RedmondWA98052,USA{reidan,kumarc}@microsoft.
comAbstract.
Weconsidertheproblemofndingdensesubgraphswithspeciedupperorlowerboundsonthenumberofvertices.
Weintro-ducetwooptimizationproblems:thedensestat-least-k-subgraphprob-lem(dalks),whichistondaninducedsubgraphofhighestaveragedegreeamongallsubgraphswithatleastkvertices,andthedensestat-most-k-subgraphproblem(damks),whichisdenedsimilarly.
Theseproblemsarerelaxedversionsofthewell-knowndensestk-subgraphprob-lem(dks),whichistondthedensestsubgraphwithexactlykvertices.
Ourmainresultisthatdalkscanbeapproximatedeciently,evenforweb-scalegraphs.
Wegivea(1/3)-approximationalgorithmfordalksthatisbasedonthecoredecompositionofagraph,andthatrunsintimeO(m+n),wherenisthenumberofnodesandmisthenumberofedges.
Incontrast,weshowthatdamksisnearlyashardtoapproximateasthedensestk-subgraphproblem,forwhichnogoodapproximationalgorithmisknown.
Inparticular,weshowthatifthereexistsapolyno-mialtimeapproximationalgorithmfordamkswithapproximationratioγ,thenthereisapolynomialtimeapproximationalgorithmfordkswithapproximationratioγ2/8.
Intheexperimentalsection,wetestthealgo-rithmfordalksonlargepubliclyavailablewebgraphs.
Weobservethat,inadditiontoproducingnear-optimalsolutionsfordalks,thealgorithmalsoproducesnear-optimalsolutionsfordksfornearlyallvaluesofk.
1IntroductionThedensityofaninducedsubgraphisthenumberofedgescontainedinthesubgraph,dividedbythenumberofvertices.
Identifyingsubgraphswithhighdensityisausefulprimitive,whichhasbeenappliedtondwebcommunities,producecompressedrepresentationsofgraphs,andidentifylinkspam[9,14,20,8].
Eectiveheuristicshavebeendevelopedtoidentifyvariouskindsofdensesubgraphs.
Kumaretal.
gaveanalgorithmforndingbipartitecliques[20].
Dourisboureetal.
gaveascalableheuristicforndingsmalldensecommunitiesinwebgraphs[9].
ThealgorithmofGibsonetal.
[14]ndsdensecommunitiesusingtwo-levelmin-hashing,withthegoalofidentifyinglinkspam.
Generallyspeaking,thesealgorithmsaredesignedtondcollectionsofsmalldensesubgraphsthatareisolatedfromeachother,whichareoftenviewedasthedensecentersofcommunitiesinthegraph.
Thisisquitedierentfromthetaskofndingasinglelargedensesubgraphthatcontainsasignicantfractionofthegraph,whichisoftenusedasamethodofpreprocessingorsubsamplingthegraph.
K.
Avrachenkov,D.
Donato,andN.
Litvak(Eds.
):WAW2009,LNCS5427,pp.
25–37,2009.
cSpringer-VerlagBerlinHeidelberg200926R.
AndersenandK.
ChellapillaThecomplexityofidentifyingdensesubgraphscanvarygreatlywhenaddi-tionalconstraintsonthesizeofthesubgraphareintroduced.
Findingthedensestsubgraphwithanarbitrarynumberofverticesisknownasthedensestsubgraphproblemds,andcanbesolvedexactlyinpolynomialtimebysolvingasequenceofmaximumowproblems[15,13].
ThealgorithmofKortsarzandPeleg[18]producesa(1/2)-approximationofthedensestsubgraphinlineartime,whichisusefulforgraphswherethetimerequiredtocomputemaximumowsispro-hibitivelylarge.
Incontrast,noecientalgorithmisknownfortheproblemofndingthedensestsubgraphwithexactlykvertices,wherekisspeciedaspartoftheinput.
Thisisthedensestk-subgraphproblem,ordks.
ThedksproblemisNP-complete,andthebestpolynomialtimealgorithmknownfordks(duetoFeige,Peleg,andKortsarz)hastheapproximationration(1/3)+δ,forasmallconstantδ[11].
Wewanttocontrolthesizeofthedensesubgraphswend,butweneedtoavoidthediculttaskofndingdensesubgraphsofaspeciedsize.
Inthispaper,weaddressthisproblembyintroducingtwovariationsofthedensestsubgraphproblem:ndingthedensestsubgraphwithatleastkvertices,andndingthedensestsubgraphwithatmostkvertices.
Werefertotheseasthedensestat-least-k-subgraphproblem(dalks),andthedensestat-most-k-subgraphproblem(damks).
Thesetworelaxedversionsofthedensestk-subgraphproblemroughlycorrespondtothetwotypesofapplicationsfordensesubgraphsdescribedearlier;forndingcommunitiesonewouldwantanalgorithmtosolvedamks,andforpreprocessingagraphonewouldwantanalgorithmfordalks.
Ourmainresultistoshowthatdalkscanbesolvedeciently,whiledamksisnearlyashardtoapproximateasdks.
InSection3,weintroducea(1/3)-approximationalgorithmfordalksthatrunsintimeO(m+n)inanunweightedgraph.
InSection4,weproveareductionthatshowsanypolynomialtimeγ-approximationalgorithmfordamkscanbeusedtodesignapolynomialtime(γ2/8)-approximationalgorithmfordks.
Ouralgorithmfordalksisbasedonthecoredecomposition,anditcanbeviewedasageneralizationofKortsarzandPeleg's(1/2)-approximationalgorithmfordens-estsubgraphproblem[18].
Thecoredecompositionwasrstintroducedasatoolforsocialnetworkanalysis[19].
Ithasbeenusedinseveralapplications,includinggraphdrawing[2]andtheanalysisofbiologicalnetworks[21].
InSection6,wepresentexperimentalresultsfordalksonpubliclyavailablewebgraphs.
Wedemonstratethatthealgorithmndssubgraphswithnearlyoptimaldensitywhileprovidingconsiderablecontroloverthesubgraphsize.
Surprisingly,weobservethatontypicalwebgraphs,thealgorithmalsoproducesagoodapproximationofthedensestsubgraphonexactlykvertices,fornearlyallvaluesofk.
InSection5,wedescribetheoreticalresultsthathelptoexplainthisobservation.
Weintroducetwographparametersbasedonthedensityofthegraph'scores.
Giventheseparameters,weproveboundsontherangeofkforwhichouralgorithmproducesagoodapproximationforthedensestk-subgraphproblem.
FindingDenseSubgraphswithSizeBounds271.
1RelatedWorkHerewesurveyresultsonthecomplexityofthedensestk-subgraphproblem.
Thebestapproximationalgorithmknownforthegeneralproblem(whenkisspeciedaspartoftheinput)isthealgorithmofFeige,Peleg,andKortsarz[11],whichhasapproximationratioO(n(1/3)+δ),forasmallconstantδ>0.
Foranyparticularvalueofk,thegreedyalgorithmofAsahiroetal.
[6]givestheratioO(k/n).
AlgorithmsbasedonlinearprogrammingandsemideniteprogramminghaveproducedapproximationratiosbetterthanO(k/n)forcertainvaluesofk,butdonotimprovetheapproximationratioforthegeneralcase[12,10].
FeigeandSeltser[12]showedthatdksisNP-completewhenrestrictedtobipartitegraphsofmaximumdegree3,byareductionfrommax-clique.
Thisreductiondoesnotproduceahardnessofapproximationresultfordks.
Infact,theyshowedthatifagraphcontainsak-clique,thenasubgraphwithkverticesand(1)k2edgescanbefoundinsubexponentialtime.
Khot[17]provedtherecanbenoPTAS(polynomialtimeapproximationscheme)forthedensestk-subgraphproblem,underareasonablecomplexityassumption.
Arora,Karger,andKarpinski[4]gaveaPTASforthespecialcasek=Ω(n)andm=Ω(n2).
Asahiro,Hassin,andIwama[5]showedthattheproblemisstillNP-completeforverysparsegraphs.
KannanandVinay[16]introducedadierentobjectivefunctionfordensity,whichisdenedforapairofvertexsubsetsSandTratherthanasinglesub-graph.
TheygaveanO(logn)-approximationforthisobjectivefunctionusingspectraltechniques.
Charikar[7]latergavealineartime(1/2)-approximational-gorithmforthisobjectivefunction,basedonthecoredecomposition,andshowedthattheproblemcanbesolvedexactlybylinearprogramming.
AlocalalgorithmforndingsmallsubgraphswithhighdensityaccordingtotheKannan-Vinayobjectivefunctionwasdescribedin[3].
2DenitionsLetG=(V,E)beanundirectedgraphwithaweightfunctionw:E→R+thatassignsapositiveweighttoeachedge.
Theweighteddegreew(v,G)isthesumoftheweightsoftheedgesinGincidentwithv.
ThetotalweightW(G)isthesumoftheweightsoftheedgesinG.
Denition1.
ForanyinducedsubgraphHofG,thedensityd(H)ofHisd(H):=W(H)|H|.
Denition2.
ForanundirectedgraphG,wedenethefollowingquantities.
Dal(G,k):=themaximumdensityofanyinducedsubgraphofGwithatleastkvertices.
Dam(G,k):=themaximumdensityofanyinducedsubgraphofGwithatmostkvertices.
28R.
AndersenandK.
ChellapillaDeq(G,k):=themaximumdensityofanyinducedsubgraphofGwithexactlykvertices.
Dmax(G):=themaximumdensityofanyinducedsubgraphofG.
Thedensestat-least-k-subgraphproblem(dalks)istondaninducedsubgraphwithatleastkverticesachievingdensityDal(G,k).
Similarly,thedensestat-most-k-subgraphproblem(damks)istondaninducedsubgraphwithatmostkverticesachievingdensityDam(G,k).
Thedensestk-subgraphproblem(dks)istondaninducedsubgraphwithexactlykverticesachievingDeq(G,k),andthedensestsubgraphproblem(ds)istondaninducedsubgraphofanysizeachievingDmax(G).
Wenowdenewhatitmeanstobeanapproximationalgorithmfordalks.
Approximationalgorithmsfordamks,dks,anddsaredenedsimilarly.
Denition3.
WesayanalgorithmA(G,k)isaγ-approximationalgorithmforthedensestat-least-k-subgraphproblemif,foranygraphGandintegerk,itreturnsaninducedsubgraphHGwithatleastkverticesanddensityd(H)≥γDal(G,k).
3FindingDenseSubgraphswithatLeastkVerticesInthissection,wedescribeanalgorithmFindLargeDenseSubgraphthatisa(1/3)-approximationalgorithmforthedensestat-least-k-subgraphproblemandthatrunsintimeO(m+n)inanunweightedgraph.
ThealgorithmisdescribedinTable1.
Themainstepofthealgorithmcomputesthecoredecompositionofthegraphusingawell-knowngreedyprocedure(see[18,7,2]).
Thisproducesanordering(v1,vn)oftheverticesofthegraph,afterwhichthealgorithmoutputsasubgraphsoftheform{v1,vj}.
KortsarzandPeleg[18]usedthecoredecompositiontogivea(1/2)-approximationalgorithmfords.
Theorem1extendstheirresulttoshowthatthecoredecompositioncanbeusedtoapprox-imatedalks.
Theorem1.
FindLargeDenseSubgraph(G,k)isa(1/3)-approximationalgo-rithmforthedensestat-least-k-subgraphproblem.
TheproofofTheorem1isinSection3.
1.
Thecoredecompositionprocedure,whichdominatestherunningtimeofFindLargeDenseSubgraph,canbeimplementedtorunintimeO(m+n)inanunweightedgraphandO(m+nlogn)inaweightedgraph.
Foraproof,wereferthereaderto[18].
Thisimpliesthefollowingproposition.
Proposition1.
TherunningtimeofFindLargeDenseSubgraph(G,k)isO(m+n)inanunweightedgraph,andO(m+nlogn)inaweightedgraph.
FindingDenseSubgraphswithSizeBounds29FindLargeDenseSubgraph(G,k):Input:agraphGwithnvertices,andanintegerk.
Output:aninducedsubgraphofGwithatleastkvertices.
1.
ComputethecoredecompositionofG:LetHn=Gandrepeatthefollowingfori=n,1,(a)LetribetheminimumweighteddegreeofanyvertexinHi.
(b)Letvibeavertexofminimumweighteddegree,wherew(vi,Hi)=ri.
(c)RemovevifromHitoformtheinducedsubgraphHi1.
(d)UpdatethevaluesofW(Hi)andd(Hi)asfollows,W(Hi1)=W(Hi)2ri,d(Hi1)=W(Hi1)/(i1).
Notethatpart1producesanorderingoftheverticesv1,vn,wherev1isthelastvertexremovedandvnistherst.
ThesetHiconsistsofthevertices{v1,vi}.
2.
OutputthesubgraphHiwiththelargestdensityd(Hi)overalli≥k.
Fig.
1.
DescriptionofFindLargeDenseSubgraph3.
1AnalysisoftheAlgorithmToanalyzeFindLargeDenseSubgraph,weconsidertherelationshipbetweenin-ducedsubgraphsofGwithhighaveragedegree(densesubgraphs)andinducedsubgraphsofGwithhighminimumdegree(w-cores).
Denition4.
GivenagraphGandaweightw∈R,thew-coreCw(G)istheuniquelargestinducedsubgraphofGwithminimumweighteddegreeatleastw.
Hereisanoutlineofhowwewillproceed.
WerstshowthattheFindLargeDenseSubgraphalgorithmcomputesallthew-coresofG(Lemma1).
WethenshowthatforanyinducedsubgraphHofGwithdensityd,the(2d/3)-coreofGhastotalweightatleastW(H)/3(Lemma2).
WeproveTheorem1usingthesetwolemmas.
Lemma1.
Let{H1,Hn},and{r1,rn}betheinducedsubgraphsandweighteddegreesdeterminedbythealgorithmFindLargeDenseSubgraphontheinputgraphG.
Foranyw∈R,letI(w)bethelargestindexsuchthatrI(w)≥w.
Then,HI(w)=Cw(G).
Inotherwords,everyw-coreofGisequaltooneofthesubgraphsHi.
Proof.
Fixavalueofw.
Iteasytosee(byinduction)thatnoneoftheverticesvn.
.
.
vI(w)+1thatwereremovedbeforevI(w)canbecontainedinaninducedsubgraphwithminimumdegreeatleastw.
ThatimpliesCw(G)HI(w).
Ontheotherhand,theminimumdegreeofHI(w)isatleastw,soHI(w)Cw(G).
Therefore,HI(w)=Cw(G).
30R.
AndersenandK.
ChellapillaLemma2.
ForanygraphGwithnnodes,totalweightW,anddensityd=W/n,thed-coreofGisnonempty.
Furthermore,foranyα∈[0,1],thetotalweightofthe(αd)-coreofGisstrictlygreaterthan(1α)W.
Proof.
Let{H1,Hn}betheinducedsubgraphsdeterminedbyFindLargeDenseSubgraphontheinputgraphG.
Fixavalueofw,andletI(w)bethelargestindexsuchthatrI(w)≥w.
RecallthatHI(w)=Cw(G)byLemma1.
SinceeachedgeinGisremovedonceduringthecourseofthealgorithm,W=ni=1ri=I(w)i=1ri+ni=I(w)+1riWw·n.
Takingw=d=W/nintheequationabove,welearnthatW(Cd(G))>0.
Takingw=αd=αW/n,welearnthatW(Cαd(G))>(1α)W.
Proof(Theorem1).
Let{H1,Hn}betheinducedsubgraphscomputedbyFindLargeDenseSubgraphontheinputgraphG.
Itsucestoshowthatforanyk,thereisanintegerI∈[k,n]satisfyingd(HI)≥Dal(G,k)/3.
LetHbeaninducedsubgraphofGwithatleastkverticesandwithdensityd=W(H)/|H|=Dal(G,k).
WeapplyLemma2toHwithα=2/3toshowthatC(2d/3)(H)hastotalweightatleastW(H)/3.
ThisimpliesthatC(2d/3)(G)hastotalweightatleastW(H)/3.
ThecoreC(2d/3)(G)hasminimumdegreeatleast2d/3,soitsdensityisatleastd/3.
Lemma1showsC(2d/3)(G)=HI,forI=|C(2d/3)(G)|.
IfI≥k,thenHIsatisestherequirementsofthetheorem.
IfIk,thenweemployasimplegreedyproceduretoreducethenumberofvertices.
WebeginwiththeinducedsubgraphUT,greedilyremovethevertexwithsmallestdegreetoobtainasmallersubgraph,andrepeatuntilexactlykverticesremain.
TheresultingsubgraphUThasdensityatleastd(UT)(k/2|UT|)bythemethodofconditionalexpectations(thistechniquewasalsousedin[11]).
ThesetUTissucientlydense:d(UT)≥d(UT)k2|UT|≥γd2k2(γ1+β)k=dγ4(γ1+β)≥dγ8max(γ1,β)=dγmin(γ,β1)8.
5FindingDenseSubgraphsofSpeciedSizeTheprevioussectionshowsthatthedensestat-least-ksubgraphproblemiseasytoapproximatewithinaconstantfactorforanygraphandanyvalueofk.
Thedensestk-subgraphproblemseemshardtoapproximatewellintheworstcase,butwemaystillbeabletondnear-optimalsolutionsforspecicinstances.
Inthissectionwedescribeamethodforidentifyingarangeofk-valuesforwhichwecanobtainagoodapproximationofthedensestk-subgraph.
Hereisanoutlineofourapproach.
Werstdeneagraphparameterk(G)∈[1,n].
Wethenprovethatforallk≥k,thealgorithmFindLargeDenseSubgraphcanbeusedtonda(1/3)-approximationofthedensestsubgraphwithexactlykvertices.
InSection6,weobserveempiricallythatforseveralexamplewebgraphs,thevalueofkisonlyasmallfractionofn.
Denition6.
ForagivengraphG,letwbethesmallestvaluesuchthattheaveragedegreeofthecoreC(w)islessthan2w.
Letk(G)=|C(w)|bethenumberofverticesinthatcore.
Roughlyspeaking,kdescribeshowsmallacoreofthegraphmustbebeforeitcanbenearlydegree-regular.
Thefollowingtheoremshowsthatforeveryk≥k,thesetHkproducedbyFindLargeDenseSubgraphhasdensityatleast1/3ofthedensestk-subgraph.
FindingDenseSubgraphswithSizeBounds33Theorem3.
Let{v1,vn}betheorderingoftheverticesproducedbyFindLargeDenseSubgraph,andletHk={v1,vk}.
Then,foranyk≥kwehaved(Hk)≥(1/3)Deq(G,k).
Proof.
Wewillrstshowthefollowing:d(Hk+1)≤d(Hk)forallk≥k.
(1)Onceweshowthis,thenforanyk≥kwehaved(Hk)=maxj≥kHj≥13Dal(k)≥13Deq(k).
ThemiddlestepfollowsfromtheapproximationguaranteeprovedinTheorem1.
Toprove(1),itsucestotakeanarbitraryvalueofwforwhich|Cw|>k,andshowthatd(Hj1)≥d(Hj)foralljintheinterval(|Cw+1|,|Cw|].
Weprovethisbyinduction,rstassumingd(Hj)≥d(Cw)andthenprovingd(Hj1)≥d(Cw).
Recallthatr(j)isthedegreeofvjinHj.
Then,d(Hj1)=j·d(Hj)2r(j)j1≥j·d(Hj)d(Hj)j1=d(Hj).
Hereweusedthefactthat2r(j)≤d(Hj).
Thisistruebecauser(j)≤w,ourassumptionthat|Cw|≥kimpliesw≤d(Cw)/2,andourinductionassumptionimpliesd(Cw)/2≤d(Hj)/2.
WhenkThefollowingboundholdsforanyk∈[1,n],andcanbecomputedeasilybyobservingthedensitiesofthesetsH1,Hn.
Lemma3.
LetRk=maxj≥kd(Hj)d(Hk).
Foranyvalueofk,wehaved(Hk)≥Rk3Deq(G,k).
Proof.
Foranyvalueofk,wehaved(Hk)=Rkmaxj≥kd(Hj)≥Rk3Dal(k)≥Rk3Deq(k).
ThemiddlestepfollowsfromtheapproximationguaranteeprovedinTheorem1.
WeremarkthattoproveTheorem3,weshowedthatRk=1forallk≥k.
InthenextsectionwewillcomputethevaluesofkandRkforseveralexamplegraphs.
6ExperimentsInthissectionwepresentexperimentalresultsonfourexamplegraphs.
ThegraphsandtheirsizesarelistedinTable1.
Threeofthesegraphsarepublicly34R.
AndersenandK.
ChellapillaTable1.
Graphsize,runningtime,andtheobservedvalueofkgraphnumnodes(n)totaldegree(2m)runningtime(sec)kdomain-200655,554,1531,067,392,106263.
819,445webbase-2001118,142,1561,985,689,782204.
57348,190uk-200539,459,9261,842,690,15692.
271368,741cnr-2000325,5586,257,4200.
35913,237Table2.
Attributesofthedensestcore,highestcore,andwcoreinthefourtestgraphsgraphcorenumbernodesincoredensityworstRkw|Cw|d(Cw)maxk≥|Cw|Rkdomain-2006wcore109994452196.
321densestcore120347372275.
96.
9694highestcore129825022072.
42.
9104webbase-2001wcore548481901089.
421densestcore228112192436.
8547highestcore228112192436.
8547uk-2005wcore258368741515.
8511densestcore10025871171.
98.
8871highestcore10025871171.
98.
8871cnr-2000wcore381323775.
11451densestcore11682161.
976.
9138highestcore11682161.
976.
9138availablewebgraphsfromtheLaboratoryforWebAlgorithmics1attheUniveritaDegliStudiDiMilano.
Thegraphwebbase-2001wasobtainedfromthe2001crawlperformedbytheWebBasecrawler.
Thegraphuk-2005wasobtainedfroma2005crawlofthe.
ukdomain,performedbyUbiCrawler.
Thegraphcnr-2000wasobtainedfromasmallcrawloftheItalianCNRdomain.
Thesegraphswerechosenbecausetheyarefairlylarge,easytoobtain,andhavebeenusedinpreviousresearchpapers.
Theremaininggraphdomain-2006isasnapshotofthedomaingraphinSeptember2006,fromMicrosoft.
Thesewereoriginallydirectedgraphs,butwehavetreatedthemasundirectedgraphsinthefollowingway.
Weconsideradirectedlinkfromavertexutoavertexvasanundirectedlinkbetweenuandv.
Weremarkthattherewillbealinkwithmultiplicity2betweenuandvinthisundirectedgraphifboth(u,v)and(v,u)appearedintheoriginaldirectedgraph.
Forthisreason,theaveragedegreeofasubgraphonkverticesmaybeaslargeas2(k1).
Inaddition,we1http://law.
dsi.
unimi.
it/FindingDenseSubgraphswithSizeBounds351001051010100101102103104Numberofverticesincorewebbase2001CorenumberAverageDegreex(1/2)100102104106100101102103Numberofverticesincorecnr2000CorenumberAverageDegreex(1/2)102104106108100101102103104Numberofverticesincoredomaingraph2006CorenumberAverageDegreex(1/2)102104106108100101102103Numberofverticesincoreuk2005CorenumberAverageDegreex(1/2)Fig.
2.
Plotsofcoresizeversuscorenumberandcoredensityinfourwebgraphsremovedallself-loopsfromthegraphs.
ThetotaldegreesreportedinTable1werecomputedafterthesemodicationsweremade.
InTable1,wereportrunningtimesforourimplementationofFindLargeDenseSubgraph.
WeimplementedthealgorithminC++,andranourexper-imentsonasinglemachinewith64GBofRAManda3.
0Ghzquad-coreIntelXeonprocessor.
Onlyoneoftheprocessorcoreswasusedbythealgorithm.
Thetimewereportisthetimerequiredtocomputethecoredecomposition,whichproducesanorderingofallverticesinthegraph.
Therunningtimedoesnotincludethetimerequiredtoloadthegraphfromdiskintomemory.
WealsoreportinTable1thevaluesofkforeachofthesegraphs.
Weobservethatkissmallcomparedtothenumberofverticesinthegraph,whichisgoodbecauseouralgorithmproducesagoodapproximationofthedensestk-subgraphforallklargerthank.
InTable2wereportstatisticsforthreespecialcoresineachoftheexamplegraphs.
Wereportthew-core(seeDenition6),whichis36R.
AndersenandK.
Chellapillathecorethatdeterminesthevalueofk.
Wereportthecorethathasthehighestdensity(densestcore),andwealsoreportthehighestvalueofwforwhichthew-coreisnonempty(highestcore).
Notethattheselasttwoarenotthesameingeneral,buttheyendupbeingthesameforthreeofourexamplegraphs.
Foreachofthesespecialcoreswereportthew-valueofthecore,thenumberofverticesinthecore,andthedensityofthecore.
ForeachofthecoresinTable2wealsoreportastatisticregardingthequantityRkdescribedinLemma3.
ForeachcoreCwwereport"worstRk",whichwedenetobethesmallestvalueofRkoverallvaluesofk≥|Cw|.
Thetableindicatesthat"worstRk"iscloseto1forthehighestcore,whichmeanswecanapproximatedkswellforallvaluesofkabovethesizeofthehighestcore.
Forexample,inthegraphdomain-2006,thehighestcorecontains2502nodesandhasavalueof.
9104forworstRk.
Thatmeansforallvaluesofk≥2502,thesetHkproducedbyFindLargeDenseSubgraphondomain-2006iswithinafactorof.
91041/3ofthedensestsubgraphonexactlykvertices,byLemma3.
Figure2containsaplotforeachofthefourwebgraphsthatshowsthesize,corenumber,anddensityofallofthegraph'scores.
Eachoftheplotsinthegurehastwocurves.
Eachpointonthecurverepresentsaw-core.
Onecurveshowsthecorenumber,theothershowsthedensityofthecore,andbothareplottedagainstthenumberofverticesinthecore.
Thevalueofkcanbeseenfromtheseplots;itisthex-coordinateoftherstpoint(fromrighttoleft)atwhichthesetwocurvesintersect.
References1.
Abello,J.
,Resende,M.
G.
C.
,Sudarsky,R.
:Massivequasi-cliquedetection.
In:Ra-jsbaum,S.
(ed.
)LATIN2002.
LNCS,vol.
2286,pp.
598–612.
Springer,Heidelberg(2002)2.
Alvarez-Hamelin,J.
I.
,Dall'Asta,L.
,Barrat,A.
,Vespignani,A.
:Largescalenet-worksngerprintingandvisualizationusingthek-coredecomposition.
AdvancesinNeuralInformationProcessingSystems18,41–50(2006)3.
Andersen,R.
:Alocalalgorithmforndingdensesubgraphs.
In:Proc.
19thACM-SIAMSymposiumonDiscreteAlgorithms(SODA2008),pp.
1003–1009(2008)4.
Arora,S.
,Karger,D.
,Karpinski,M.
:PolynomialtimeapproximationschemesfordenseinstancesofNP-hardproblems.
In:Proc.
27thACMSymposiumonTheoryofComputing(STOC1995),pp.
284–293(1995)5.
Asahiro,Y.
,Hassin,R.
,Iwama,K.
:Complexityofndingdensesubgraphs.
Dis-creteAppl.
Math.
121(1-3),15–26(2002)6.
Asahiro,Y.
,Iwama,K.
,Tamaki,H.
,Tokuyama,T.
:Greedilyndingadensesub-graph.
J.
Algorithms34(2),203–221(2000)7.
Charikar,M.
:Greedyapproximationalgorithmsforndingdensecomponentsinagraph.
In:Jansen,K.
,Khuller,S.
(eds.
)APPROX2000.
LNCS,vol.
1913,pp.
84–95.
Springer,Heidelberg(2000)8.
Buehrer,G.
,Chellapilla,K.
:Ascalablepatternminingapproachtowebgraphcompressionwithcommunities.
In:WSDM2008:Proceedingsoftheinternationalconferenceonwebsearchandwebdatamining,pp.
95–106(2008)9.
Dourisboure,Y.
,Geraci,F.
,Pellegrini,M.
:Extractionandclassicationofdensecommunitiesintheweb.
In:WWW2007:Proceedingsofthe16thinternationalconferenceonWorldWideWeb,pp.
461–470(2007)FindingDenseSubgraphswithSizeBounds3710.
Feige,U.
,Langberg,M.
:Approximationalgorithmsformaximizationproblemsarisingingraphpartitioning.
J.
Algorithms41(2),174–211(2001)11.
Feige,U.
,Peleg,D.
,Kortsarz,G.
:Thedensek-subgraphproblem.
Algorith-mica29(3),410–421(2001)12.
Feige,U.
,Seltser,M.
:Onthedensestk-subgraphproblem,Technicalreport,De-partmentofAppliedMathematicsandComputerScience,TheWeizmannInstitute,Rehobot(1997)13.
Gallo,G.
,Grigoriadis,M.
,Tarjan,R.
:Afastparametricmaximumowalgorithmandapplications.
SIAMJ.
Comput.
18(1),30–55(1989)14.
Gibson,D.
,Kumar,R.
,Tomkins,A.
:Discoveringlargedensesubgraphsinmassivegraphs.
In:Proc.
31stVLDBConference(2005)15.
Goldberg,A.
:Findingamaximumdensitysubgraph,TechnicalReportUCB/CSB84/171,DepartmentofElectricalEngineeringandComputerScience,UniversityofCalifornia,Berkeley,CA(1984)16.
Kannan,R.
,Vinay,V.
:Analyzingthestructureoflargegraphs(manuscript)(1999)17.
Khot,S.
:RulingoutPTASforgraphmin-bisection,densek-subgraph,andbipar-titeclique.
SIAMJournalonComputing36(4),1025–1071(2006)18.
Kortsarz,G.
,Peleg,D.
:Generatingsparse2-spanners.
J.
Algorithms17(2),222–236(1994)19.
Seidman,S.
B.
:Networkstructureandminimumdegree.
SocialNetworks5,269–287(1983)20.
Kumar,R.
,Raghavan,P.
,Rajagopalan,S.
,Tomkins,A.
:TrawlingtheWebforemergingcyber-communities.
In:Proc.
8thWWWConference(WWW1999)(1999)21.
Wuchty,S.
,Almaas,E.
:Peelingtheyeastproteinnetwork.
Proteomics5,444(2005)