MINISTRY OF EDUCATION VIETNAM ACADEMY OF AND TRAINING SCIENCE AND TECHNOLOGY GRADUATE UNIVERSITY OF SCIENCE AND TECHNOLOGY Hoang Duc Anh MODULARITY AND RANDOM WALKS IN COMMUNITY DETECTION Major : Applied Mathematics Code: 8 46 01 12 MASTER’S THESIS IN MATHEMATICS ADVISOR: Assoc. Phan Thi Ha Duong Hanoi — 2022 Declaration I hereby declare that this thesis and the work presented in it are the result of my own study. Whenever the works of others are involved, every effort has been made to give credit clearly, with due references to the literature. I confirm that this thesis has not been previously included in a thesis or dissertation submitted for a degree or any other qualification at this graduate university or any other institution.
I take full responsibility for the above declaration. Student Hoang Duc Anh Acknowledgements I would like to express a deep gratitude to my advisor, Assoc. Phan Thi Ha Duong, who introduced me to network science and has provided me with support and guidance throughout my study. Her encouragement and enthusiasm for research have been a constant source of inspiration for me throughout the project.
I would like to thank the researchers at the Institute of Mathematics and the group Mathematical Foundation for Computer Science for having created a wonderful envi- ronment for young students like me. I also thank the lecturers and administrative staff at the Institute as well as the Graduate University of Science and Technology for their valuable lessons and dedicated help during my degree. I would like to acknowledge the generous support of Vingroup JSC, who has funded my study for the last two years. I was supported by the Master, PhD Scholarship Programme of Vingroup Innovation Foundation (VINIF), Institute of Big Data, codes VINIF.
Contents 1 Acknowledgements 2 3 List of Figures 5 Introduction 6 Notations and conventions 8 N WORKS AND COMMUN 5 9 11 On network science).3 The topics of this thesis}.1 Definition of modularity]. HQ HH kg KV 20 [2.3 Modularity in community detection|.1 Random walks and stochastic matricel].3 ‘The Walktrap algorithm).1 Summary of the thesis).2 Some further directions]. 200022 ee ee 63 Bibliography) |A A Python implementation of Walktrap] 65 71 on List of Figures [L1 A graph with two communities].2 Some common network structures|.1 Effect of the resolution parameter.2 Significance of modularity on a graph with two balanced groups).3 Significance of modularity on a graph with two unbalanced groups.4 Significance of modularlty on a cycle|.1 Spectral properties of a graph with two balanced groups.2 Spectral properties of a graph with three balanced groups.3 Spectral properties of a graph with two unbalanced groups].4 Spectral properties of a graph with three unbalanced groups.5 Spectral properties of a near-bipartite graph|.6 Illustration of Ward and single linkage agglomerative clustering on a | Walktrap matrix].7 Testing Walktrap on graphs with two balanced groups] .8 Testing Walktrap on graphs with three balanced groups.9 Testing Walktrap on graphs with two unbalanced groups.10 Testing Walktrap on graphs with two unbalanced groups with different | Le 57 [3.11 Testing Walktrap on graphs with three unbalanced groups].12 Testing Walktrap on graphs with three unbalanced groups with different | ¬ 59 |B.13 Testing Walktrap on near-bipartite graphs|.14 Testing the consistency of Walktrap|. 61 Introduction Due to the rise of Big Data phenomenon and interdisciplinary research, network science emerged and has drawn enormous interest from both academia and industry.
Dividing a network into smaller groups of similar nodes - a task called community detection - is one direction that has yielded valuable insights about complex network data. In this master’s thesis, we study two topics in the field of community detection: a quality function called modularity, and clustering properties of the random walk eigenvectors of a graph. This thesis contains four chapters and one appendix. The main content is in Chap- ter [2]and Chapter e Chapter |1| briefly discusses some notable features of network science and commu- nity structure in order to situate the main topics of the thesis.
e Chapter |2] is a detailed exposition of modularity - a popular clustering quality function. Section defines modularity and gives the standard interpretation based on a random graph model. Section 22-3] presents basic properties of modu- larity, including modularity of some special graphs (cycles, complete multipartite graphs, .3] explains several shortcomings of modularity when used in the practical context of community detection. ° Chapter|3|sbudies the spectral properties of the random walk matrix and a cluster- ing algorithm based on those properties.]] introduces the random walk matrix and its spectrum.2|explains why the top eigenvectors of that ma- trix inherit the clustering structure of the graph and illustrates the phenomenon visually.3] presents the Walktrap algorithm and performs experiments on some random graphs to investigate the effect of step size and linkage method in the algorithm.
° Chapter [J] summarizes the main content of the thesis and introduces some further directions. ° Appendix [A] provides a simple Python implementation of the Walktrap algorithm introduced in Chapter This is an expository thesis. Our main contribution lies in collecting and organizing several results scattered in the literature; we try to provide more detail in theoretical explanations and proofs, and illustrate various ideas using our own experiments imple- mented in the Python programming language (more detail can be found in Chapter|4). We hope this document could be a useful starting point for people studying the two main topics mentioned above.
Notations and conventions In this thesis, ‘graph’ and ‘network’ are used interchangeably. Unless stated otherwise, we work with simple undirected graphs, i. undirected graphs with no parallel edges and no self-loops. For a graph G, let V(G) and E(G) be the vertex set and edge set of G; sometimes we simply use V and EF if the underlying graph G is clear from context.
For a vertex subset P C V(G), let E(P) be the set of edges lying inside P and let e(P) := |E(P)|. We also define the volume of P to be the sum of the degrees of the vertices inside P: vol(P) := » deg(v). ueP In case there are many graphs under consideration, we put G in the subscripts, like eq(P), volg(P), ., P,} of a set V is a collection of disjoint non-empty subsets whose union is V, that is Pj P; =9@ for alli A j and LỆ 1P; =V. All vectors are column vectors.
The transpose of matrix M is denoted by M', and similarly the transpose of vector x is a’ (which is a row vector). We use 1 to denote a vector with all entries equal to 1, whose dimension should be clear from context. In many places we use subscripts to index vectors, so round brackets are used for vector entries: x;(w) is the u-th entry of vector 2;. Chapter 1 NETWORKS AND COMMUNITIES This short chapter introduces some notable features of network science and community structure in order to set the background for the main topics of the thesis.1 On network science Network science has grown to an enormous discipline, and it is certainly outside of this chapter’s scope to even attempt a small survey.
Instead, we only explain a few features that can be confusing for beginners. There are currently several good textbooks on network science; among them, we mention [1] with a broad coverage, and [2| with a unique focus on modeling, interpretation, and data quality. One attempt at defining network science can be found in the editorial [3]: network science is the study of network models. A network model is a network representation of something, comprising two main components: abstraction from real phenomena to network concepts, and representation of those concepts by network data.
What distin- guishes network data from traditional tabular data is that there is some dependency (or relationship) built in, most easily visualized as links (or edges) in a graph. Whether a relationship should be represented by a network, and then how it can be represented, depend a lot on the problem being studied; see Chapters 5 and 11 of [2] for more detailed introduction. There are several reasons, both commercial and scientific, for the increased interest in network science in recent decades. A popular reason, which is also the one most easily capturing the public imagination, is the rise of the Internet and big social media 10 networks, whose links are given concrete names like ‘tag’, ‘friend’, ‘follower’,.
Another big spur to the study of networks is how they can be used to tackle complexity in various scientific disciplines. This approach introduced a new paradigm in science, called topological explanations by philosophers |4], complementing existing kinds of explanations like mechanistic, causal, probabilistic,. See the surveys [5] [6] for more details on how networks can be used to model complexity. One notable feature of network science is how scattered the literature is (as can be shown by a brief look at the bibliography of this thesis).
Outside from a few recent network-specific journals, network science articles appear in journals and conferences of physics, computer science, mathematics, statistics, as well as sociology. Inevitably, there are different cultures and methods. The traditional divide is between social scien- tists coming from social network analysis, and natural scientists coming from physics. Social scientists study small, carefully curated networks in very specific contexts.
They have very rich notions of links and care about the motivation of actors in the networks. In contrast, physicists are inspired by statistical physics and complexity, hence they search for ‘universal laws’ in large collections of large networks, abstracted from those networks’ context. This divide is discussed in [7 [8] [2} Chapter 2]. A slightly dif ferent but related contrast is between those searching for universality independent of particular objects, and statisticians who focus on testable properties in real data.
The division leads to the controversy of power-law degree distribution, carefully recounted in [9]. Finally, there are also computer scientists and mathematicians, each with their own approaches [10]. All of this make network science a ‘trading zone’ [9], where cross-fertilization of ideas as well as cultural clashes happen.2 Community structure Given a network, it is natural to find groups of similar nodes, and we say those groups form a community structure. That description is certainly vague, because we do not (and probably should not) have precise conditions for when nodes form a community.
The task of discerning those groups in a network is called community detection or graph clustering; those two terms are used interchangeably in this thesis. Graph clustering is closely related to tabular data clustering. Indeed, one popular way of clustering tabular data is spectral clustering: we create a graph where nodes represent data points, connect two nodes if they are ‘close’ enough, then use spectral properties of the graph to cluster data (see the surveys mentioned in Section of 11 this thesis). Conversely, graph embedding is a method of handling very large graphs by embedding vertices in low dimensional euclidean spaces before applying standard techniques of tabular data (see [11] for a recent survey of this big field).
Defining communities There is no single, unified concept of a community; see IILB] and II] for many definitions. Some define communities using numerical characteristics like edge density or a quality function. Other take a procedural approach and define communities as results of community detection algorithms; in other words, the algorithms become implicit models of communities. There are also the issues of whether communities can be overlapped, and difference between global (discovering all communities) and local (finding communities in a small region only) methods.
For the purposes of Chapter [2] and Chapter [B|in this thesis, a community is a group of vertices which has higher internal density than external density, and a community structure is a partition of the vertex set (in particular, we do not consider overlap- ping communities). Figure its adjacency matrix, generated using the stochastic block model.