multicomodo官网

Preprintof:MartinAtzmueller(2017)DescriptiveCommunityDetection.
In:RokiaMissaoui,SergeiObiedkov,SergeiKuznetsov(eds.
)FormalConceptAnalysisinSocialNetworkAnalysis.
Springer,Berlin/Heidelberg(InPress)DescriptiveCommunityDetectionMartinAtzmuellerAbstractSubgroupdiscoveryandcommunitydetectionarestandardapproachesforidentifying(cohesive)subgroups.
Thispaperpresentsanorganizedpictureofrecentresearchindescriptivecommunity(andsubgroup)detection.
Here,itsummarizesapproachesfortheidenticationofdescriptivepatternstargetingbothstaticaswellasdynamic(sequential)relations.
Wespecicallyfocusonattributedgraphs,i.
e.
,complexrelationalgraphsthatareannotatedwithadditionalinformation.
Thisre-latestoattributeinformation,forexample,assignedtothenodesand/oredgesofthegraph.
Combiningsubgroupdiscoveryandcommunitydetection,wealsosumma-rizeanefcientandeffectiveapproachfordescriptivecommunitydetection.
1IntroductionSubgroupdiscovery(Klsgen,1996;Wrobel,1997;Atzmueller,2015b)aimsatidentifyinginterestingdescriptivesubgroupscontainedinadataset-fromacom-positionalnetworkanalysisview,aimingatadescriptiongiven,e.
g.
,byasetofattributevalues.
Thesubgroupsareidentiedinsuchawaythattheyareinterest-ingwithrespecttoacertaintargetproperty.
Inthecontextofubiquitousdataandsocialmedia,interestingtargetconceptsaregiven,e.
g.
,bybinaryvariablesforob-tainingcharacteristicdescriptionsofcertainphenomena,denselyconnectedgraphstructures(communities)orexceptionalspatio-semanticdistributions(Atzmueller,2014,2016b).
Thisdirectlybridgesthegaptocommunitydetectionmethods(New-manandGirvan,2004;Fortunato,2010;Xieetal,2013)thatfocusonstructuralaspectsofanetwork/graph,forndingdenselyconnectedsubgroupsofnodes.
TilburgUniversity,TilburgCenterforCognitionandCommunication(TiCC),UniversityofKassel,ResearchCenterforInformationSystemDesign(ITeG)e-mail:m.
atzmuller@uvt.
nl12MartinAtzmuellerThispaper,anextendedandsignicantlyrevisedversionof(Atzmueller,2015a)presentsanorganizedpictureofrecentresearchinsubgroupdiscoveryandcom-munitydetectionspecicallyfocusingonattributedgraphs.
Westartwiththein-troductionofnecessarybackgroundconceptsinSection2.
Afterthat,weprovideacompactoverviewonprominentmethodsforcommunitydetection,anddiscusstheexceptionalmodelminingapproach.
Next,Section3describesrecentworkonminingattributedgraphsfordescription-orientedapproaches.
Then,Section4sum-marizestheCOMODOalgorithmcombiningbothcommunitydetectionandsub-groupdiscoveryinadescription-orientedapproach(AtzmuellerandMitzlaff,2011;Atzmuelleretal,2016a),forwhichwealsodescribeanextensionforsequentialpat-ternmining.
Finally,weconcludewithasummaryandpointoutinterestingfuturedirectionsinSection5.
2SubgroupDiscoveryIngeneral,subgroupdiscoverycanbeappliedforanystandarddatasetintabularforminastraight-forwardmannerusingavailableefcientalgorithms,e.
g.
,(Atz-mueller,2015b),asimplementedintheVIKAMINE(AtzmuellerandPuppe,2005;AtzmuellerandLemmerich,2012)platform.
Also,forcompositionalanalysisofso-cialnetworks,i.
e.
,wherenodeshaveattachedattributeinformation,wecandirectlyapplysubgroupdiscoveryforidentifyinginterestingsubgroupsofnodesaccordingtoagivenqualitymeasure.
Thedescriptionspaceisthengivenbyallthecompo-sitionalvariablesandtheirrespectivevaluedomains.
Aswewillseebelow,itisalsopossibletocombineastructuralwithacompositionalanalysisofanetwork,resultingindescription-orientedcommunitydetectionusingsubgroupdiscovery.
2.
1PatternsandSubgroupsBasicconceptsusedinsubgroupdiscovery(Klsgen,1996;Wrobel,1997;Atz-mueller,2015b)arepatternsandsubgroups.
Intuitively,apatterndescribesasub-group,i.
e.
,thesubgroupconsistsofinstancesthatarecoveredbytherespectivepattern.
Itiseasytosee,thatapatterndescribesaxedsetofinstances(subgroup),whileasubgroupcanalsobedescribedbydifferentpatterns,coveringthesubgroup'instances.
Below,wedenetheseconceptsmoreformally.
AdatabaseD=(I,A)isgivenbyasetofindividualsIandasetofattributesA.
Aselectororbasicpatternselai=vjisaBooleanfunctionI→{0,1}thatistrueifthevalueofattributeai∈Aisequaltovjfortherespectiveindividual.
Foranumericattributeanumwhoserangeisdividedintointervalsej=[minj,maxj]selectorsselanum∈[minj;maxj]canbedenedforeachinterval[minj;maxj]inthedomainofanum.
TheBooleanfunctionisthensettotrueifthevalueofattributeanumiswithintherespectiveinterval.
ThesetofallbasicpatternsisdenotedbyS.
DescriptiveCommunityDetection3Denition1.
Asubgroupdescriptionor(complex)patternsdisgivenbyasetofbasicpatternssd={sel1,sell},whereseli∈S,whichisinterpretedasaconjunction,i.
e.
,sd(I)=sel1sell,withlength(sd)=l.
Withoutlossofgenerality,wefocusonaconjunctivepatternlanguageusingnominalattribute–valuepairsasdenedaboveinthispaper;internaldisjunctionscanalsobegeneratedbyappropriateattribute–valueconstructionmethods,ifnec-essary(AtzmuellerandPuppe,2006).
Wecallapatternpasuperpattern(orrene-ment)ofasubpatternps,iffpsp.
Denition2.
Asubgroup(extension)sgsd:=ext(sd):={i∈I|sd(i)=true}isthesetofallindividualswhicharecoveredbythepatternsd.
Assearchspaceforsubgroupdiscoverythesetofallpossiblepatterns2Sisused,thatis,allcombinationsofthebasicpatternscontainedinS.
Then,appropriateefcientalgorithms,e.
g.
,(Atzmueller,2015b)canbeapplied.
2.
2InterestingnessofaPatternAlargenumberofqualityfunctionshasbeenproposedintheliterature,see(GengandHamilton,2006)foracomprehensivelist,inordertoestimatetheinteresting-nessofapatternselectedaccordingtotheanalysistask.
Denition3.
Aqualityfunctionq:2S→Rmapseverypatterninthesearchspacetoarealnumberthatreectstheinterestingnessofapattern(ortheextensionofthepattern,respectively).
Manyqualityfunctionsforasingletargetconcept(e.
g.
,binary(Klsgen,1996;Atzmueller,2015b)ornumerical(Atzmueller,2015b;Lemmerichetal,2016)),tradeoffthesizen=|ext(sd)|ofasubgroupforthedeviationtsdt0,wheretsdistheaveragevalueofagiventargetconceptinthesubgroupidentiedbythepatternsdandt0theaveragevalueofthetargetconceptinthegeneralpopulation.
Inthebinarycase,theaveragesrelatetotheshareofthetargetconcept.
Thus,typicalqualityfunctionsareoftheformqa(sd)=na·(tsdt0),a∈[0;1].
(1)Forbinarytargetconcepts,thisincludes,forexample,theweightedrelativeaccu-racyforthesizeparametera=1orasimpliedbinomialfunction,fora=0.
5.
Multi-targetconcepts,e.
g.
,(Klsgen,2002a,b;Atzmuelleretal,2015;Atzmueller,2015b)thatdeneatargetconceptcapturedbyasetofvariablescanbedenedsimilarly,e.
g.
,byextendinganunivariatestatisticaltesttothemultivariatecase,4MartinAtzmuellere.
g.
,(Atzmuelleretal,2015):Then,themultivariatedistributionsofasubgroupandthegeneralpopulationarecomparedinordertoidentifyinterestingpatterns.
Whileaqualityfunctionprovidesarankingofthediscoveredsubgrouppatterns,oftenalsoastatisticalassessmentofthepatternsisusefulindataexploration.
Qual-ityfunctionsthatdirectlyapplyastatisticaltest,forexample,theChi-squarequal-ityfunction,e.
g.
,(Atzmueller,2015b)provideap-valueforsimpleinterpretation.
However,theChi-squarequalityfunctionestimatesdeviationsintwodirections.
Analternative,whichcanalsobedirectlymappedtoap-valueisgivenbytheadjustedresidualqualityfunctionqr,sincethevaluesofqrfollowalargestandardnormaldistribution(Agresti,2007):qr=n(tsdt0)·1nt0(1t0)(1nN)(2)Theresultoftop-ksubgroupdiscoveryisthesetofthekpatternssd1,sdk,wheresdi∈2S,withthehighestinterestingnessaccordingtotheappliedqual-ityfunction.
Asubgroupdiscoverytaskcannowbespeciedbythe5-tuple:(D,c,S,q,k),wherecindicatesthetargetconcept;thesearchspace2SisdenedbythesetofbasicpatternsS.
Forseveralqualityfunctionsoptimisticestimates(Grosskreutzetal,2008;Atz-mueller,2015b)canbeappliedfordeterminingupperqualitybounds:Considerthesearchforthekbestsubgroups:Ifitcanbeproventhatnosubsetofthecurrentlyinvestigatedhypothesisisinterestingenoughtobeincludedintheresultsetofksub-groups,thenwecanskiptheevaluationofanysubsetsofthishypothesis,butcanstillguaranteetheoptimalityoftheresult.
Moreformally,anoptimisticestimateoe(q)ofaqualityfunctionqisafunctionsuchthatpp→(oe(q))(p)≥q(p),i.
e.
,suchthatnorenementpofthepatternpcanexceedthequalityobtainedby(oe(q))(p).
2.
3CommunityDetectionCommunitiesandcohesivesubgroupshavebeenextensivelystudiedinsocialsci-ences,e.
g.
,usingsocialnetworkanalysismethods(WassermanandFaust,1994).
Communitydetectionmethodscanbeclassiedaccordingtoseveraldimensions,e.
g.
,disjointvs.
overlappingcommunities.
Here,actorsinanetworkcanonlybelongtoexactlyonecommunity,ortomultiplecommunitiesatthesametime.
Furthermore,wedistinguishbetweenmethodsthatworkonextended(attributed)graphs,i.
e.
,includingdescriptiveinformationaboutthenodes.
Below,weprovideanoverviewonrepresentativemethods,includingseveralbasicmethodsworkingonsimplegraphs.
Afterthat,weelaborateonmethodsfordetectingoverlappingcommunities,beforewefocusondescriptivemethods.
DescriptiveCommunityDetection52.
3.
1BasicsofCommunityDetectionWassermanandFaust(1994)discusssocialnetworkanalysisindepthandprovideanoverviewontheanalysisofsubgroups/communitiesingraphs,includingclique-based,degree-basedandmatrix-perturbation-basedmethods.
Furthermore,severalalgorithmsforcommunitydetectionhavebeenproposed,formalizingthenotionsofinterestingcommunitystructures,andintroducingthemodularityqualitymea-sure(Newman,2004;NewmanandGirvan,2004;Newman,2006).
Fortunato(2010)presentsathoroughsurveyonthestateoftheartcommunitydetectionalgorithmsingraphs,focussingondetectingdisjointcommunities.
Forassessingthequalityofacommunity,usuallynotonlythedensityofthecommunityisassessedbuttheconnectiondensityofthecommunityiscomparedtothedensityoftherestofthenetwork(NewmanandGirvan,2004).
Forthemodu-laritymeasurethenumberofconnectionswithinthecommunityiscomparedtothestatistically"expected"numberbasedonallavailableconnectionsinthenetwork.
Besidesmodularity,prominentexamplesofcommunityqualitymeasuresincludeforexample,thesegregationindex(Freeman,1978)andtheinvertedaverageout-degreefraction(YangandLeskovec,2012).
2.
3.
2DetectingOverlappingCommunitiesOverlappingcommunitiesallowanextendedmodelingofactor–actorrelationsinsocialnetworks:Nodesofacorrespondinggraphcanthenparticipateinmultiplecommunities.
Thisisalsotypicallyobservedinreal-worldnetworksregardingdif-ferentcomplementaryfacetsofsocialinteractions(Pallaetal,2005).
AgeneraloverviewonalgorithmsforoverlappingcommunitydetectionisprovidedbyXieetal.
Xieetal(2013).
Forexample,cliquepercolationmethodsproposedin(Pallaetal,2005,2007)detectk-cliquesandthenmergethemintooverlappingcommuni-ties.
XieandSzymanski(2013)presentmethodsthatextendtheideaoflabelprop-agation(Raghavanetal,2007).
(Lancichinettietal,2009)describeanapproachforoverlappingandhierarchicalcommunitystructureusingalocalcommunitymetric.
Thepresentedmetricitselfiscomputedlocallybutstillassessesaglobalclustering.
FurtherstatisticalandlocaloptimizationalgorithmsincludetheCOPRA(Gregory,2010)algorithmbyGregoryusinglabel-propagationofneighboringnodesuntilaconsensusisreached,andtheMOSES(McDaidandHurley,2010)algorithmbyMcDaidandHurleyusingstatisticalmodel-basedtechniques.
Concerningqualitymeasures,extensionsofthemodularitymetricforhandlingoverlappingcommuni-tiesaredescribedin(Muffetal,2005;Nicosiaetal,2009;Linetal,2009).
6MartinAtzmueller2.
4ExceptionalModelMiningAgeneralframeworkformulti-targetqualityfunctionsinsubgroupdiscoveryisgivenbyexceptionalmodelmining(Lemanetal,2008;Atzmueller,2015b):Ittriestoidentifyinterestingpatternswithrespecttoalocalmodelderivedfromasetofattributes.
Theinterestingnesscanbedened,e.
g.
,byasignicantdeviationfromamodelthatisderivedfromthetotalpopulationortherespectivecomplementsetofinstanceswithinthepopulation.
Ingeneral,amodelconsistsofaspecicmodelclassandmodelparameterswhichdependonthevaluesofthemodelattributesintheinstancesoftherespectivepatterncover.
Thequalitymeasureqthendeterminestheinterestingnessofapatternaccordingtoitsmodelparameters.
Following(Lemmerichetal,2012),weoutlinesomesimpleexamplesbelow,focusingonrelationsbetweenpairs(correlation)andsetsofvariables(logisticregression):Arelativelysimpleexampleforanexceptionalitymeasureconsidersthetaskofidentifyingsubgroupsinwhichthecorrelationbetweentwonumericattributesisespeciallystrong,e.
g.
,asmeasuredbythePearsoncorrelationcoefcient.
Thiscorrelationmodelclasshasexactlyoneparameter,i.
e.
,thecorrelationco-efcient.
Furthermore,usingasimplelinearregressionmodel,wecancomparetheslopesoftheregressionlinesofthesubgrouptothegeneralpopulationorthesub-groups'complement.
Thissimplelinearregressionmodelshowsthedepen-dencybetweentwonumericvariablesxandy:Itisbuiltbyttingastraightlineinthetwodimensionalspacebyminimizingthesquaredresidualsejofthemodel:yi=a+b·xi+ejTheslopeb=cov(x,y)var(x)computedgiventhecovariancecov(x,y)ofxandy,andthevariancevar(x)ofxcanthenbeusedforidentifyinginterestingpatterns(Lemanetal,2008).
Thelogisticregressionmodelisusedfortheclassicationofabinarytargetattributey∈Tfromasetofindependentbinaryattributesxj∈T\y,j=1,T|1.
Themodelisgivenby:y=11+ez,z=b0+jbjxj.
Interestingpatternsarethenthose,forexample,forwhichthemodelparametersbjdiffersignicantlyfromthosederivedfromthetotalpopulation.
DescriptiveCommunityDetection7Consideringnetworkstructures,wecanalsoadaptexceptionalmodelminingtothatsetting.
Essentially,itcanberegardedasadescription-orientedapproachforassessingnetworkstructures,ifthepatternsareusedtoinducegraphsorsub-graphs.
Aswewilldiscussbelow,wecanthenalsoapplyexceptionalmodelminingfordescriptivecommunitydetection,inessencecombiningsubgroupdiscoveryandcommunitydetectionintoauniedapproach.
Below,werstoutlineaqualityfunctionforcomparinggraphstructuresthatcorrespondtoindividualpatterns(QAP).
Afterthat,wediscussqualityfunctionsusedincommunitydetectioninordertoassesssubgraphsthatareinducedbysomecriterion,e.
g.
,byadescriptivepattern.
Forsomenotation,wefollowthenotionspresentedin(Atzmuelleretal,2016a):Asoutlinedabove,theconceptofacommunityintuitivelydescribesagroupCofin-dividualsoutofapopulationsuchthatmembersofCarestrongly"related"amongeachotherbutweakly"related"toindividualsoutsideofC.
Byintuition,thisre-lates,forexample,tostronglyconnectedgroupsofactorsinsocialnetworks.
ThisideatranslatestocommunitiesasvertexsetsCVofagraphG=(V,E).
Todeterminetheamountofrelatedness(orconnectedness,andthus,thecommunityqualityofsuchasubset)severalmeasureshavebeenproposed.
Forfurtherconceptsregardingourterminologyandalsothestandardcommunityqualityfunctionsoutlinedbelow,wefollowthenotationintroducedin(Atzmuelleretal,2016a):ForagivenundirectedgraphG=(V,E)andacommunityCV:n:=|V|,letm:=|E|,nC:=|C|,mC:=|{{u,v}∈E:u,v∈C}|–thenumberofintra-edgesofC,andmC:=|{{u,v}∈E:|{u,v}∩C|=1}|–thenumberofinter-edgesofC.
Here,itisalsoconvenienttointroduceaninter-degreeforanodeu∈C(thatdependsonthechoiceofC)bydC(u):=|{{u,v}∈E:v/∈C}|,countingthenumberofedgesbetweenuandnodesoutsideofC,andd(u)u,v}∈E}|isthedegreeofnodeu.
Thereisawiderangeofdifferentcommunityevaluationfunctions2V→Rforestimatingthecommunityquality.
Inthecontextofthispaper,wefocusonmaximizinglocalqualityfunctionsforsinglecommunities(whichareinducedbyspecicpatterns).
Therefore,weconsidertheinverseofaqualitymeasureinthosecases,wherethemeasureitselfindicateshigherqualitybylowervalues.
Concerningnetworkstructures,wecancompareadjacencymatricesinducedbyaspecicpattern,see(Atzmueller,2016a).
Fortheassessmentwecanapply,forexample,thequadraticassignmentprocedure(Krackhardt,1987)(QAP):itisastandardapproachforcomparingnetworkstructures,e.
g.
,usingagraphcorrelationmeasure:ForcomparingtwographsG1andG2,itestimatesthecorrelationoftherespectiveadjacencymatricesM1andM2andteststhatgraphlevelstatisticagainstaQAPnullhypothesis(Krackhardt,1987).
QAPcomparestheobservedgraphcorrelationof(G1,G2)tothedistributionoftherespectiveresultingcorrelationscoresobtainedonrepeatedrandomrowandcolumnpermutationsoftheadjacencymatrixofG2.
Asaresult,weobtainacorrelationandastatisticalsignicancelevelaccordingtotherandomizeddistributionscores.
8MartinAtzmuellerForderivingaqualitymeasurebasedonQAPandgraphcorrelation,wecom-parethereferencematrixMNandthematrixMPforpatternP:qQ(P)=QAP(MN,MP)=cov(MN,MP)var(MN)·var(MP),whereMNisthetransitionmatrixinducedbysomereferencemodel(see(Atz-muelleretal,2016d;Atzmueller,2016a)),andMPisthetransitionmatrixin-ducedbypatternP,covindicatesthecovarianceofthematrices,andvar(M)=cov(M,M)thevarianceForanin-depthdescriptionofQAP,wereferto(Krackhardt,1987).
Further-more,forthetransitionmatrix,wereferto(Atzmuelleretal,2016c,d)formoredetailsonthematrixconstructionstep.
Regardingthequalityofasubgraphinducedbyapattern,wecanadaptthewellknownmodularitymeasuretotheideaofassessingtheinducedsubgraphcap-turedbyalocalpattern,i.
e.
,acommunitypattern(withanassociatedsubgroupdescription).
Ingeneral,themodularityMOD(Newman,2004;NewmanandGirvan,2004;Newman,2006)ofagraphclusteringwithkcommunitiesC1,CkVfocusesonthenumberofedgeswithinacommunityandcomparesthatwiththeexpectedsuchnumbergivenanull-model(i.
e.
,acorrespondingrandomgraphwherethenodedegreesofGarepreserved).
ItisgivenbyMOD=12mu,v∈VAu,vd(u)d(v)2mδ(C(u),C(v)),(3)whereC(i)denotesfori∈Vthecommunitytowhichnodeibelongs.
δ(C(u),C(v))istheKroneckerdeltasymbolthatequals1ifC(u)=C(v),and0otherwise.
So,themodularityassessesthecommunityqualityofagraphpartitioning,butcanalsobeadaptedtooverlappingcommunities,e.
g.
,(Muffetal,2005;Nicosiaetal,2009;Linetal,2009)forconsideringthecompletegraphstructure.
Forexceptionalmodelmining,however,weneedtoconsiderindividualpat-terns.
Inordertofocusonasubgraphinducedbyapattern,themodularitycon-tributionofasinglecommunityCinalocalcontext(subgraphinducedbythenodescontainedinthecommunityC)canthenbecomputed(Newman,2006;Nicosiaetal,2009)as:MODL(C)=12mu,v∈CAu,vd(u)d(v)2m,yieldingMODL(C)=2mC2mu,v∈Cd(u)d(v)4m2=mCmu,v∈Cd(u)d(v)4m2.
DescriptiveCommunityDetection9ThesegregationindexSIDX(Freeman,1978)isanotherprominentmeasurefromcommunitydetection.
Itfocusesonthelocalcontributionofthepattern,andcomparesthenumberofexpectedinter-edgestothenumberofobservedinter-edges,normalizedbytheexpectation:SIDX(C)=E(mC)mCE(mC)=1mCn(n1)2mnC(nnC)(4)Finally,theInverseAverage-ODF(out-degreefraction)IAODF(YangandLeskovec,2012)capturesthebasicintuitionofacommunityregardingthecontainedvs.
theoutgoingedgesdiscussedabove.
Asanotherlocalmeasure,IAODFcomparesthenumberofinter-edgestothenumberofalledgesofacommunityC,andaveragesthisforthewholecommunitybyconsideringthefractionforeachindividualnode:IAODF(C):=11nCu∈CdC(u)d(u)(5)3CommunityDetectionandDescriptionWhilethecommunitydetectionmethodsdescribedaboveonlyfocusonthegraphstructure,richergraphrepresentations,i.
e.
,attributedgraphs,enableapproachesthatspecicallyexploitthedescriptiveinformationofthelabelsassignedtonodesand/oredgesofthegraph.
Nodesofanetworkrepresentingusers,forexample,canbelabeledwithtagsthattherespectiveusersutilizedinsocialbookmarkingsystems,ornodes(denotingactors)canbelabeledwithpropertiesofthelatter.
Then,explicitdescriptionsforthecharacterizationofacommunitycanbeprovided.
Concerningmethodsthatfocusonsuchdescriptionsingeneral,anapproachforcommunitydetectionusingfeaturesidentiedbyfrequentpatternminingispre-sentedin(Adnanetal,2009);closedfrequentpatternsarederivedandarethenusedforcreatingasocialnetworkmodelbasedonanentropyanalysis.
However,thenet-workstructureitselfisnotexploited.
Similarly,Seseetal(2010)extractssubgraphswithcommonitemsets.
Givenalabeledgraph,itemset-sharingsubgraphscanthenbeenumerated.
However,thisapproachalsodoesnotconsiderthedensityofgraphs,noranycommunitymeasures.
Focusingonmethodsforgeneratingexplicitdescriptionsconnectedwiththegraphstructure,wedistinguishbetweentwotypesofapproaches:rst,methodsthatmainlyworkonthegraphstructurebutapplydescriptiveinformationforre-strictingthepossiblesetsofcommunities;second,methodsthatminedescriptivepatternsforobtainingcommunitycandidatesevaluatedusingthegraphstructure.
Asarepresentativeofthersttype,theconceptsofdensesubgraphsandsubspaceclustersforminingcohesivepatternsarecombinedin(Moseretal,2009).
10MartinAtzmuellerStartingwithquasi-cliques,theseareexpandeduntilconstraintsregardingthedescriptionorthegraphstructureareviolated.
Similarly,Günnemannetal(2013)combinessubspaceclusteringanddensesubgraphmining,alsointerleavingquasi-cliqueandsubspaceconstruction.
Asanexampleforthesecondtypeoutlinedabove,Galbrunetal(2014)proposesanapproachfortheproblemofndingoverlappingcommunitiesingraphsandsocialnetworksthataimsatdetectingthetop-kcom-munitiessuchthatthetotaledgedensityoverallkcommunitiesismaximized.
ThethreealgorithmicvariantsproposedinGalbrunetal(2014)applyagreedystrat-egyfordetectingdensesubgroups,andrestricttheresultsetofcommunities,suchthateachedgecanbelongtoatmostonecommunity.
Thispartitioninginvolvesaglobalapproachonthecommunityquality.
Furthermore,Silvaetal(2012)studythecorrelationbetweenattributesetsandtheoccurrenceofdensesubgraphsinlargeattributedgraphs.
Theproposedmethodconsidersfrequentattributesetsusinganadaptedfrequentitemminingtechnique,andidentiesthetop-kdensesubgraphsinducedbyaparticularattributeset,calledstructuralcorrelationpatterns.
TheDCMmethodpresentedin(Pooletal,2014)includesatwo-stepprocessofcommunityde-tectionandcommunitydescription.
Aheuristicapproachisappliedfordiscoveringthetop-kcommunities.
Pooletal.
utilizeaspecialinterestingnessfunctionwhichisbasedoncountingoutgoingedgesofacommunitysimilartotheIAODFmea-sure;forthat,theyalsodemonstratethetrendofacorrelationwiththemodularityfunction.
Furthermore,theCOMODOalgorithm(Atzmuelleretal,2016a)thatwesum-marizeinthenextsectioncombinescommunitydetectionandsubgroupdiscoveryresultinginadescription-orientedapproach.
Byspecifyingastandardqualityfunc-tionthequalityofthecommunitiestodiscovercanbeestimated.
Then,thisqualityfunctioncanbespecicallyselectedaccordingtotheanalysistask.
4CommunityDetectionusingExceptionalModelMiningForprovidingbothstructurallyvalidandinterpretablecommunitiesweutilizethegraphstructureaswellasadditionaldescriptivefeaturesofthenodes.
Hence,weidentifycommunitiesassetsofnodestogetherwithadescriptioncomposedofthenodes'features.
Suchacommunitypatternthenprovidesanintuitivedescriptionofthecommunity,e.
g.
,byaneasilyinterpretableconjunctionofattribute-valuepairs.
Basically,weaimatidentifyingcommunitiesaccordingtostandardcom-munityqualitymeasures.
Below,werstprovideanalgorithmicoverviewontheapproachandsummarizeexemplaryevaluationresults.
Afterthat,wesketchtheap-plicationofthealgorithmforcommunitydetectionondynamicnetworks,i.
e.
,foridentifyingexceptionalsequentialpatterns.
DescriptiveCommunityDetection114.
1COMODO:Description-OrientedCommunityDetectionBelow,wesummarizetheCOMODOalgorithmpresentedin(Atzmuelleretal,2016a):Itfocusesondescription-orientedcommunitydetectionusingsubgroupdis-covery,andaimsatdiscoveringthetop-kcommunities(describedbycommunitypatterns).
Themethodisbasedonanadaptedsubgroupdiscoveryapproach(Atz-muellerandMitzlaff,2011;Lemmerichetal,2012),andalsotacklestypicalprob-lemsthatarenotaddressedbystandardapproachesforcommunitydetectionsuchaspathologicalcaseslikesmallcommunitysizes.
COMODOutilizesoptimistices-timates(Grosskreutzetal,2008;Wrobel,1997),whichareefcienttocompute,inordertoprunethesearchspacesignicantly.
Forthat,anumberofstandardcom-munityevaluationfunctionshavebeenappliedusingoptimisticestimatesforanefcientapproach.
4.
1.
1AlgorithmicOverviewCOMODOutilizesboththegraphstructure,aswellasdescriptiveinformationoftheattributedgraph.
Thisinformationiscontainedintwodatastructures:ThegraphstructureisencodedingraphGwhiletheattributeinformationiscontainedindatabaseDdescribingtherespectiveattributevaluesofeachnode.
Inaprepro-cessingstep,wemergethesedatasources.
Sincethecommunitiesconsideredinourapproachdonotcontainisolatednodes,wecandescribethemassetsofedges.
Wetransformthedata(ofthegivengraphGandthedatabaseDcontainingthenodes'descriptiveinformation)intoanewdatasetfocusingontheedgesofthegraphG:Eachdatarecordinthenewdatasetrepresentsanedgebetweentwonodes.
Theattributevaluesofeachsuchdatarecordarethecommonattributesoftheedge'stwonodes.
Foramoredetaileddescription,wereferto(Atzmuelleretal,2016a).
COMODOutilizesanextendedFP-tree(frequentpatterntree)structureinspiredbytheFP-growthalgorithm,whichcompilesthedatainaconvenientprexpatterntreestructureforminingfrequentitemsets,see(AgrawalandSrikant,1994)foradetaileddescription.
Ouradaptedtreestructureiscalledthecommunitypatterntree(CP-tree)thatallowstoefcientlytraversethesolutionspace.
Thetreeisbuiltintwoscansofthegraphdatasetandisthenminedinarecursivedivide-and-conquermanner,see(AtzmuellerandLemmerich,2009;Lemmerichetal,2012)formoredetails.
InthemainalgorithmicprocedureofCOMODO,patternscontainingonlyonebasicpatternareminedrst.
Then,patternsconditionedontheoccurrenceofa(prexed)complexpattern(asasetofbasicpatterns,choseninthepreviousrecur-sionstep)areconsideredrecursively.
Formorealgorithmicdetails,wereferto(Atz-muelleretal,2016a).
Asdescribedthere,wecanapplystandardqualityfunctionsefcientlyusingoptimisticestimates,e.
g.
,forthemodularityorthesegregationindex,see(Atzmuelleretal,2016a)formoredetails.
12MartinAtzmueller4.
1.
2IllustrativeEvaluationResultsBelow,wepresentillustrativeevaluationresults(Atzmuelleretal,2016a)consider-ingtheefciencyoftheappliedoptimisticestimates,andthevalidityoftheobtainedpatterns.
Forthat,wecomparedthetotalnumberofsearchsteps,thatiscommunityallocationsthatareconsideredbytheCOMODOalgorithm,withnooptimistices-timatepruningtooptimisticestimatepruningusingdifferentcommmunityqualitymeasures.
Additionally,wemeasuredtheimpactofusingdifferentminimalcommu-nitysizethresholds.
SomeresultsareshowninFigure1fortheBibSonomyclickgraphfork=10,20,50andminimalsizethresholdsτn=10,20.
Weconsideranumberofstandardcommunityqualityfunctions,thatis,thesegregationindex,theInverseAverage-ODF,andthemodularity.
Fig.
1RuntimeperformanceofCOMODOontheBibSonomyclickgraph,see(Atzmuelleretal,2016a)formoredetails:Searchstepswithnooptimisticestimatepruning(NOP)vs.
communityqualityfunctionswithoptimisticestimatepruning:MODL(Localmodularity),SIDX(SegregationIndex)andIAODF(InverseAverage-ODF),forminimalsizethresholdsτn=10,20.
Thelarge,exponentialsearchspacecanbeexemplied,e.
g.
,fortheclickgraphwithatotalofabout2·1010searchstepsforaminimalcommunitysizethresh-oldτn=10.
Theresultsdemonstratetheeffectivenessoftheproposeddescrip-tiveminingapproachapplyingthepresentedoptimisticestimates.
Theimplementedpruningschememakestheapproachscalableforlargerdatasets,especiallywhenthelocalmodularityqualityfunctionischosentoassessthecommunities'quality.
Concerningthevalidityofthepatterns,wefocusedonstructuralpropertiesofthepatternsandthesubgraphsinducedbytherespectivecomunitypatterns.
Weappliedthesignicancetestdescribedin(Koyuturketal,2007)fortestingthestatisticalsignicanceofthedensityofadiscoveredsubgraph.
Furthermore,wecomparedCOMODOtothreebaselinecommunitydetectionalgorithms(McDaidandHurley,2010;Gregory,2010;Pooletal,2014),whereCOMODOconsistentlyshowsasig-nicantlybetterperformanceconcerningvalidityanddescriptionlength;formoredetails,wereferto(Atzmuelleretal,2016a).
DescriptiveCommunityDetection134.
2SequentialPatternAnalysis:DetectingExceptionalLinkTrailsInadditiontostaticcommunitydetection,wecanalsoconsidertemporalaspects,i.
e.
,focusingonsequencesofstatesoreventswhichcanbeappliedforavarietyofanalysisrangingfromtheanalysisofhumanbehavior(Atzmuelleretal,2016c)toindustrialapplications(Atzmuelleretal,2016d).
Inanextendedmodelingapproach,wecanmaptransitionsbetweenstatestoaweightednetwork,accordingtoarstorderMarkovchainmodel.
Below,weoutlineanapproachfordetectingexceptionalsequentiallinktrailscapturedbycommunitypatterns,see(Atzmueller,2016a)foradetaileddescription.
Asbefore,oursubjectofanalysisisgivenbyanattributedgraphthatmodelsthelinktrailsinthefollowingway:Nodesofthegraphdenoteactorsofasocialnetwork,e.
g.
,usersofasocialsystemorlocationsinalocation-basedsocialnetwork.
Theedgesofthegraphmodelthelinksbetweenthenodes(astransitions).
Asasimpleexample,wecanconsiderasetofusersandasetoflocations.
Eachuservisitsasequenceoflocations–inalocation-basedsocialnetwork.
Then,weareinterestedinmodelingthesesequences(oflocations),andindetectingexceptionalgroupsoftransitions(betweenlocations)w.
r.
t.
usersandtheirproperties,respectively.
Atamusiceventfestival,forexample,possiblecharacterizingfactorsdescribingcertainusersgroupscouldbespecicmusicgenres.
Here,exceptionalpatternscouldinclude,forexample,usersbeinginterestedinrockmusicanddancevisitingonlyaveryspecicselectionofperformancesincharacteristicsequences,comparedtothebehaviorofallusersandtheirsequentiallinktrails.
Essentially,weapplydescriptivecommunitydetection(e.
g.
,usingCOMODO)ontheattributedgraph,wheretheedgesindicatetransitionsbetweenstatesaccordingtoarst-orderMarkovchainmodelingapproach(LempelandMoran,2000;Singeretal,2014).
4.
2.
1ModelingForourattributedgraphmodel,welabelthelinksaccordingtothedescriptivein-formationofthesequentialtrail.
Then,weidentifyexceptionalcommunitypatternsbasedonthelabelsandstructureofthecontainedlinksusingexceptionalmodelmining.
Inparticular,weassessapatterncapturingasetofnodesthatmodelthestatespaceoftherespectivetransitions.
Forconstructingareferencemodel,weconstructtransitionmatricescorrespond-ingtotheobserveddata.
Forthoseobservedsequenceswecansimplyconstructtransitionmatricescountingthetransitionsbetweentheindividualstates.
Wecon-structanaccordingmatrixMNwithmNij=|suc(i,j)|,wheresuc(i,j)denotesthesuccessivesequencesfromstateitostatejcontainedinthesequence.
AcommunitypatternPinducesasubgraph(community)CPgivenasetoflabelsP,selectingalllinksthatarecovered,i.
e.
,thatsharealabelcontainedinP.
Then,alltransitionsinthematrixMNareselected(correspondingtoasetoflinksofthenetwork)thatarecoveredbythepatternP.
Usingthat,weconstructanaccordingtransitionpatternmatrixMPbasedontherespectivecountsofthecoveredtransi-14MartinAtzmuellertions.
Intuitively,thematrixMPcanthenberegardedassomekindof"projection"ofmatrixMNgiventhepatternPusingourmodelingapproach.
Inthesimplestcase,wecanjusttransfertheweightedlinksofthesubgraphCP.
Foridentifyingexceptionalmodels(MPinducedbyP)wecanthenapply,e.
g.
,theQAPqualityfunctionqQ(P)=QAP(MN,MP)introducedabove.
4.
2.
2ResultsForsomeillustrativeresults(see(Atzmueller,2016a)formoredetails),weuti-lizeddatafromtheEveryAware1project,e.
g.
,(Atzmuelleretal,2014).
Specif-ically,wefocusedoncollectivelyorganizednoisemeasurementscollectedusingtheWideNoisePlusapplicationbetweenDecember14,2011andJune6,2014,seeAtzmuelleretal(2015)formoredetails.
WideNoisePlusallowsthecollec-tionofnoisemeasurementsusingsmartphones.
ItincludessensordatafromthemicrophonegivenasnoiselevelindB(A),thelocationfromtheGPS-,GSM-,andWLAN-sensorrepresentedaslatitudeandlongitudecoordinate,aswellasatimes-tamp.
Inaddition,tagscanbeassignedtotherecording.
WecollecteddatafromallaroundtheworldusingiOSandAndroiddevices.
Table1Illustrativeexceptionalconforming/deviatingcommunitypatternsforWideNoisePlus.
Patterns#1-#3tendrathertoconformtothereferencemodel(especially#1and#2),whilepatterns#4-#5(increasingly)showadeviatingbehavior.
#qQSizeDescription10.
945078trafc20.
893990car30.
763326noise40.
43707bird∧courtyard50.
24600background∧quietIntotal,theapplieddatasetcontains6,069datarecords,i.
e.
,noisemeasure-mentsof635users(i.
e.
,635trails,withanaveragetraillengthofabout10)and2,009distincttags.
Table1showsexemplaryexceptionalconforminganddeviatingpatternsusingqQasqualitymeasure.
Inaddition,itshowsthesizesofthecoveredsubsets.
Fromaqualitativepointofview,thepatternsshowninthetableareintuitivetointerpretandalsotendtoconformtoourexpectationsconcerningthereferencebehaviorofthedataset,wherewecanclearlyidentifydeviationsconcerningnoisyandrelativelyquietenvironments.
1http://www.
everyaware.
euDescriptiveCommunityDetection155ConclusionsInthispaper,wehavepresentedanorganizedviewondescriptivecommunityde-tection.
Specically,wedescribedsubgroupdiscoveryforcompositionalnetworkanalysisconcerningpropertiesoftheactors,withextensionstotheanalysisofcom-plextargetconceptslikecorrelationsbetweenasetofvariables,ordensesubgraphs–capturedbyexceptionalmodelminingapproaches.
Then,thisdirectlyextendstocommunitydetectiononattributedgraphs.
Inparticular,wesummarizedtheCOMODOalgorithmthatcombinescommunitydetectionandexceptionalmodelmining,resultinginadescription-orientedapproachforcommunityanalytics.
Wefurthermoresketchedanextensiontodynamicdata,consideringsequentialpatternscapturingexceptionalsequentiallinktrails.
Thisaddsonefurtherdimensiontothedescriptiveapproaches,byconsideringbystaticaswellasdynamicphenomena,andenablesthemodelingandinvestigationofcomplexanalysistasks.
Forfuturework,weaimtoextendtheanalysistowardsfurthertime-orientedrepresentations,e.
g.
,consideringsequencesofgraphs,andtheevolutionofcom-munities,e.
g.
,(Kibanovetal,2014,2015).
Also,weaimtointegrateandexploitmethodsforgeneratingdescriptionsandtherespectiverelationsinlinkanalytics,e.
g.
,inlinkprediction(Scholzetal,2012,2013a,b)onmultiplexnetworks.
Then,besidesthedetectionofcommunities,alsotheiranalysisandassessmentintheformofdescriptivepatternsishighlyrelevant,e.
g.
,(Atzmuelleretal,2005,2006;Atz-muellerandPuppe,2008;AtzmuellerandLemmerich,2013)alsoconcerningtheirsemanticgrounding(Mitzlaffetal,2013,2014),andintegrationintoexplanation-awareapproaches(Clancey,1983;Roth-BerghoferandCassens,2005;AtzmuellerandRoth-Berghofer,2010).
Furthermore,developingscalablemethodsforenablingsuchapproachesforlargeandcomplexdatasets,e.
g.
,(Lemmerichetal,2012;Atz-muelleretal,2016b)areanotherinterestingdirectionforfuturework.
ReferencesAdnanM,AlhajjR,RokneJ(2009)IdentifyingSocialCommunitiesbyFrequentPatternMining.
In:Proc.
13thIntl.
Conf.
InformationVisualisation,IEEEComputerSociety,Washington,DC,USA,pp413–418AgrawalR,SrikantR(1994)FastAlgorithmsforMiningAssociationRules.
In:BoccaJB,JarkeM,ZanioloC(eds)Proc.
20thInt.
Conf.
VeryLargeDataBases,(VLDB),MorganKaufmann,pp487–499AgrestiA(2007)AnIntroductiontoCategoricalDataAnalysis.
Wiley-BlackwellAtzmuellerM(2014)DataMiningonSocialInteractionNetworks.
JournalofDataMiningandDigitalHumanities1AtzmuellerM(2015a)SubgroupandCommunityAnalyticsonAttributedGraphs.
In:KuznetsovSO,MissaouiR,ObiedkovS(eds)Proc.
InternationalWorkshoponSocialNetworkAnalysisusingFormalConceptAnalysis(SNAFCA-2015),CEUR-WS,vol1534AtzmuellerM(2015b)SubgroupDiscovery–AdvancedReview.
WIREs:DataMiningandKnowl-edgeDiscovery5(1):35–4916MartinAtzmuellerAtzmuellerM(2016a)DetectingCommunityPatternsCapturingExceptionalLinkTrails.
In:Proc.
IEEE/ACMASONAM,IEEEPress,Boston,MA,USAAtzmuellerM(2016b)LocalExceptionalityDetectiononSocialInteractionNetworks.
In:Proc.
ECML-PKDD2016:EuropeanConferenceonMachineLearningandPrinciplesandPracticeofKnowledgeDiscoveryinDatabases,SpringerVerlag,BerlinAtzmuellerM,LemmerichF(2009)FastSubgroupDiscoveryforContinuousTargetConcepts.
In:Proc.
InternationalSymposiumonMethodologiesforIntelligentSystems,Springer,Hei-delberg,Germany,LNCS,vol5722,pp1–15AtzmuellerM,LemmerichF(2012)VIKAMINE-Open-SourceSubgroupDiscovery,PatternMining,andAnalytics.
In:Proc.
EuropeanConferenceonMachineLearningandPrinciplesandPracticeofKnowledgeDiscoveryinDatabases,Springer,Heidelberg,GermanyAtzmuellerM,LemmerichF(2013)ExploratoryPatternMiningonSocialMediausingGeo-ReferencesandSocialTaggingInformation.
InternationalJournalofWebScience2(1/2)AtzmuellerM,MitzlaffF(2011)EfcientDescriptiveCommunityMining.
In:Proc.
24thInterna-tionalFLAIRSConference,AAAIPress,PaloAlto,CA,USA,pp459–464AtzmuellerM,PuppeF(2005)Semi-AutomaticVisualSubgroupMiningusingVIKAMINE.
Jour-nalofUniversalComputerScience11(11):1752–1765AtzmuellerM,PuppeF(2006)SD-Map-AFastAlgorithmforExhaustiveSubgroupDiscov-ery.
In:Proc.
EuropeanConferenceonPrinciplesandPracticeofKnowledgeDiscoveryinDatabases(PKDD),Springer,Heidelberg,Germany,pp6–17AtzmuellerM,PuppeF(2008)ACase-BasedApproachforCharacterizationandAnalysisofSub-groupPatterns.
JournalofAppliedIntelligence28(3):210–221AtzmuellerM,Roth-BerghoferT(2010)TheMiningandAnalysisContinuumofExplainingUn-covered.
In:Proc.
30thSGAIInternationalConferenceonArticialIntelligence(AI-2010)AtzmuellerM,BaumeisterJ,HemsingA,RichterEJ,PuppeF(2005)SubgroupMiningforInter-activeKnowledgeRenement.
In:Proc.
10thConferenceonArticialIntelligenceinMedicine(AIME05),Springer,Heidelberg,Germany,LNAI3581,pp453–462AtzmuellerM,BaumeisterJ,PuppeF(2006)IntrospectiveSubgroupAnalysisforInteractiveKnowledgeRenement.
In:Proc.
19thInternationalFloridaArticialIntelligenceResearchSocietyConference2006(FLAIRS-2006),AAAIPress,PaloAlto,CA,USA,pp402–407AtzmuellerM,BeckerM,KibanovM,ScholzC,DoerfelS,HothoA,MacekBE,MitzlaffF,MuellerJ,StummeG(2014)UbiconanditsApplicationsforUbiquitousSocialComputing.
NewReviewofHypermediaandMultimedia20(1):53–77AtzmuellerM,MuellerJ,BeckerM(2015)Mining,ModelingandRecommending'Things'inSocialMedia,Springer,Heidelberg,Germany,chapExploratorySubgroupAnalyticsonUbiq-uitousData.
No.
8940inLNAIAtzmuellerM,DoerfelS,MitzlaffF(2016a)Description-OrientedCommunityDetectionusingExhaustiveSubgroupDiscovery.
InformationSciences329:965–984AtzmuellerM,MollenhauerD,SchmidtA(2016b)BigDataAnalyticsUsingLocalExceptional-ityDetection.
In:EnterpriseBigDataEngineering,Analytics,andManagement,IGIGlobal,Hershey,PA,USAAtzmuellerM,SchmidtA,KibanovM(2016c)DASHTrails:AnApproachforModelingandAnal-ysisofDistribution-AdaptedSequentialHypothesesandTrails.
In:Proc.
WWW2016(Com-panion),IW3C2/ACMAtzmuellerM,SchmidtA,KloepperB,ArnuD(2016d)HypGraphs:AnApproachforModelingandComparingGraph-BasedandSequentialHypotheses.
In:Proc.
ECML-PKDDWorkshoponNewFrontiersinMiningComplexPatterns(NFMCP),RivadelGarda,ItalyClanceyWJ(1983)TheEpistemologyofaRule-BasedExpertSystem:AFrameworkforExpla-nation.
ArticialIntelligence20:215–251FortunatoS(2010)CommunityDetectioninGraphs.
PhysicsReports486(3-5):75–174FreemanL(1978)SegregationInSocialNetworks.
SociologicalMethods&Research6(4):411GalbrunE,GionisA,TattiN(2014)OverlappingCommunityDetectioninLabeledGraphs.
DataMinKnowlDiscov28(5-6):1586–1610DescriptiveCommunityDetection17GengL,HamiltonHJ(2006)InterestingnessMeasuresforDataMining:ASurvey.
ACMComput-ingSurveys38(3)GregoryS(2010)FindingOverlappingCommunitiesinNetworksbyLabelPropagation.
NewJPhys(12)GrosskreutzH,RüpingS,WrobelS(2008)TightOptimisticEstimatesforFastSubgroupDis-covery.
In:Proc.
EuropeanConferenceonMachineLearningandPrinciplesandPracticeofKnowledgeDiscoveryinDatabases,Springer,Heidelberg,Germany,LNCS,vol5211,pp440–456GünnemannS,FrberI,BodenB,SeidlT(2013)GAMer:ASynthesisofSubspaceClusteringandDenseSubgraphMining.
In:KnowledgeandInformationSystems,SpringerKibanovM,AtzmuellerM,ScholzC,StummeG(2014)TemporalEvolutionofContactsandCommunitiesinNetworksofFace-to-FaceHumanInteractions.
ScienceChina57KibanovM,AtzmuellerM,IlligJ,ScholzC,BarratA,CattutoC,StummeG(2015)IsWebContentaGoodProxyforReal-LifeInteractionACaseStudyConsideringOnlineandOfineInter-actionsofComputerScientists.
In:Proc.
IEEE/ACMInternationalConferenceonAdvancesinSocialNetworksAnalysisandMining(ASONAM),IEEEPress,Boston,MA,USAKlsgenW(1996)Explora:AMultipatternandMultistrategyDiscoveryAssistant.
In:FayyadUM,Piatetsky-ShapiroG,SmythP,UthurusamyR(eds)AdvancesinKnowledgeDiscoveryandDataMining,AAAIPress,pp249–271KlsgenW(2002a)HandbookofDataMiningandKnowledgeDiscovery,OxfordUniversityPress,NewYork,chap16.
3:SubgroupDiscoveryKlsgenW(2002b)HandbookofDataMiningandKnowledgeDiscovery,OxfordUniversityPress,NewYork,chap5.
2:SubgroupPatternsKoyuturkM,SzpankowskiW,GramaA(2007)AssessingSignicanceofConnectivityandCon-servationinProteinInteractionNetworks.
JournalofComputationalBiology14(6):747–764KrackhardtD(1987)QAPPartiallingasaTestofSpuriousness.
SocialNetworks9:171–186LancichinettiA,FortunatoS,KertJ(2009)DetectingtheOverlappingandHierarchicalCommu-nityStructureinComplexNetworks.
NewJournalofPhysics11(3)LemanD,FeeldersA,KnobbeA(2008)ExceptionalModelMining.
In:Proc.
EuropeanConfer-enceonMachineLearningandPrinciplesandPracticeofKnowledgeDiscoveryinDatabases,Springer,LectureNotesinComputerScience,vol5212,pp1–16LemmerichF,BeckerM,AtzmuellerM(2012)GenericPatternTreesforExhaustiveExceptionalModelMining.
In:Proc.
EuropeanConferenceonMachineLearningandPrinciplesandPrac-ticeofKnowledgeDiscoveryinDatabases,Springer,Heidelberg,GermanyLemmerichF,AtzmuellerM,PuppeF(2016)FastExhaustiveSubgroupDiscoverywithNumericalTargetConcepts.
DataMiningandKnowledgeDiscovery30:711–762LempelR,MoranS(2000)TheStochasticApproachforLink-StructureAnalysis(SALSA)andtheTKCEffect.
ComputerNetworks33(1):387–401LeskovecJ,LangKJ,DasguptaA,MahoneyMW(2008)CommunityStructureinLargeNetworks:NaturalClusterSizesandtheAbsenceofLargeWell-DenedClusters.
CoRRabs/0810.
1355LinYR,ChiY,ZhuS,SundaramH,TsengBL(2009)AnalyzingCommunitiesandTheirEvolu-tionsinDynamicSocialNetworks.
ACMTransKnowlDiscovData3:8:1–8:31McDaidA,HurleyN(2010)DetectingHighlyOverlappingCommunitieswithModel-BasedOver-lappingSeedExpansion.
In:Proc.
InternationalConferenceonAdvancesinSocialNetworksAnalysisandMining,IEEEComputerSociety,Washington,DC,USA,ASONAM,pp112–119MitzlaffF,AtzmuellerM,StummeG,HothoA(2013)SemanticsofUserInteractioninSocialMedia.
In:GhoshalG,Poncela-CasasnovasJ,TolksdorfR(eds)ComplexNetworksIV,StudiesinComputationalIntelligence,vol476,Springer,Heidelberg,GermanyMitzlaffF,AtzmuellerM,HothoA,StummeG(2014)TheSocialDistributionalHypothesis.
Jour-nalofSocialNetworkAnalysisandMining4(216)MoserF,ColakR,RaeyA,EsterM(2009)MiningCohesivePatternsfromGraphswithFeatureVectors.
In:SDM,SIAM,vol9,pp593–604MuffS,RaoF,CaischA(2005)LocalModularityMeasureforNetworkClusterizations.
PhysicalReviewE(Statistical,Nonlinear,andSoftMatterPhysics)72(5):056,10718MartinAtzmuellerNewmanME,GirvanM(2004)FindingandEvaluatingCommunityStructureinNetworks.
PhysRevEStatNonlinSoftMatterPhys69(2):1–15NewmanMEJ(2004)DetectingCommunityStructureinNetworks.
EuropPhysicalJ38NewmanMEJ(2006)ModularityandCommunityStructureinNetworks.
ProceedingsoftheNa-tionalAcademyofSciences103(23):8577–8582NicosiaV,MangioniG,CarchioloV,MalgeriM(2009)ExtendingtheDenitionofModularitytoDirectedGraphswithOverlappingCommunities.
JStatMechp03024PallaG,DeriI,FarkasI,VicsekT(2005)UncoveringtheOverlappingCommunityStructureofComplexNetworksinNatureandSociety.
Nature435(7043):814–818PallaG,FarkasIJ,PollnerP,DerenyiI,VicsekT(2007)DirectedNetworkModules.
NewJournalofPhysics9(6):186PoolS,BonchiF,vanLeeuwenM(2014)Description-drivenCommunityDetection.
TransactionsonIntelligentSystemsandTechnology5(2)RaghavanU,RA,KumaraS(2007)NearLinearTimeAlgorithmtoDetectCommunityStructuresinLarge-ScaleNetworks.
PhysRevE76:036106Roth-BerghoferTR,CassensJ(2005)Mappinggoalsandkindsofexplanationstotheknowledgecontainersofcase-basedreasoningsystems.
In:Muoz-AvilaH,RicciF(eds)Case-BasedReasoningResearchandDevelopment,6thInternationalConferenceonCase-BasedReason-ing,ICCBR2005,Chicago,IL,USA,August2005,Proceedings,SpringerVerlag,Heidelberg,no.
3620inLectureNotesinArticialIntelligenceLNAI,pp451–464ScholzC,AtzmuellerM,StummeG(2012)OnthePredictabilityofHumanContacts:InuenceFactorsandtheStrengthofStrongerTies.
In:Proc.
4thASE/IEEEInternationalConferenceonSocialComputing(SocialCom),IEEEComputerSociety,Boston,MA,USAScholzC,AtzmuellerM,BarratA,CattutoC,StummeG(2013a)NewInsightsandMethodsForPredictingFace-To-FaceContacts.
In:KicimanE,EllisonNB,HoganB,ResnickP,SoboroffI(eds)Proc.
InternationalAAAIConferenceonWeblogsandSocialMedia,AAAIPress,PaloAlto,CA,USAScholzC,AtzmuellerM,KibanovM,StummeG(2013b)HowDoPeopleLinkAnalysisofContactStructuresinHumanFace-to-FaceProximityNetworks.
In:Proc.
ASONAM2013,ACMPress,NewYork,NY,USASeseJ,SekiM,FukuzakiM(2010)MiningNetworkswithSharedItems.
In:Proc.
19thACMInternationalConferenceonInformationandKnowledgeManagement,ACM,NewYork,NY,USA,pp1681–1684SilvaA,MeiraJrW,ZakiMJ(2012)MiningAttribute-StructureCorrelatedPatternsinLargeAttributedGraphs.
ProcVLDBEndowment5(5):466–477SingerP,HelicD,TaraghiB,StrohmaierM(2014)DetectingMemoryandStructureinHumanNavigationPatternsUsingMarkovChainModelsofVaryingOrder.
PLOSONE9(7)WassermanS,FaustK(1994)SocialNetworkAnalysis:MethodsandApplications,1stedn.
No.
8inStructuralAnalysisintheSocialSciences,CambridgeUniversityPressWrobelS(1997)AnAlgorithmforMulti-RelationalDiscoveryofSubgroups.
In:Proc.
1stEuro-peanSymposiumonPrinciplesofDataMiningandKnowledgeDiscovery,Springer,Heidel-berg,Germany,pp78–87XieJ,SzymanskiBK(2013)LabelRank:AStabilizedLabelPropagationAlgorithmforCommu-nityDetectioninNetworks.
In:Proc.
IEEENetworkScienceWorkshop,WestPoint,NYXieJ,KelleyS,SzymanskiBK(2013)OverlappingCommunityDetectioninNetworks:TheState-of-the-artandComparativeStudy.
ACMComputSurv45(4):43:1–43:35YangJ,LeskovecJ(2012)DeningandEvaluatingNetworkCommunitiesBasedonGround-truth.
In:Proc.
ACMSIGKDDWorkshoponMiningDataSemantics,ACM,NewYork,NY,USA,MDS'12,pp3:1–3:8