StructureandFunctionofComplexModularNetworksJor¨ gReichardtAugust2006StructureandFunctionofComplexModularNetworksVomFachbereichfur¨ PhysikundElektrotechnikderUniversitat¨ BremenzurErlangungdesGradesDoktorderNaturwissenschaften(Dr. rer. nat.)genehmigteDissertationvonDipl. Phys. Jor¨ gReichardtausZwickau1.Gutachter: Prof.Dr.StefanBornholdt2. Prof.Dr.KlausPawelzikAlle großen Wahrheiten sind in Wirklichkeitvollig¨ banal. Eskommtlediglichdaraufan,sieimmerwiederaufparadoxeWeisezuerzahlen,¨damitsienichtinVergessenheitgeraten.JoseSaramago,“DerDoppelganger¨ ”AbstractSubject of this thesis is the development of physics based methods for graph cluster-ing or community detection and the assessment of the statistical significance of theresults through comparison to appropriate random null models. After a brief intro ductiontotheproblemofdataclusteringingeneralandgraphclusteringinparticularthe reader is introduced to some of the basic terms and notations of graph theoryand some fundamental questions of concern in the study of complex networks and anumber of examples where community detection is applied are given. In the follow ing,variousdefinitionsofcommunitiescomingfromsociology,computerscienceandphysics are reviewed and the diverse algorithms to detect community structure anddiscusses their merits and shortcomings. The discussion shows that the concept of“community” or cluster in a network is only vaguely defined.