Topic outline

  • Networks, Types of networks: Technological networks, Social networks, Information networks, Biological networks.

    In this section we define the notion "network", then we consider types of networks with many different examples such as Internet, telephone networks, power grids, transportation networks, friendship networks, affiliation networks, citation and co-citation networks, World Wide Web, neural networks, metabolic networks, ecological networks, etc. Next, we will consider each of the type of the networks in details, in particular, we will present main features of these networks and describe the techniques used to measure their structure. 

  • Mathematics of Networks

    In this section we mainly consider the mathematical tools used in the study of networks. In particular, we will introduce the basic theoretical tools used to describe and analyze networks, most of which come from Graph Theory. We first consider various networks (weighted, directed, underlying, acyclic, bipartite, planar) and their representation. Then we will consider degrees, in-degrees, out-degrees, mean degrees, degree sequences, degree correlation and density. Next, we will focus on metric parameters of the networks such as eccentricity, radius, diameter, average path length, etc. Further we will consider components of networks (weakly connected components, strongly connected components, In-components, Out-components, etc). We will also present some results on the connectivity of networks that concern independent paths, cut sets, flows. Finally, we will discuss several applications of the graph Laplacian in networks and random walks on networks.

  • Measures and Metrics

    In this section we mainly consider standard measures and metrics for quantifying network structure. We begin our consideration with various centralities such as degree centrality, eigenvector centrality, Katz centrality, PageRank, closeness centrality, betweenness centrality, etc. Then we will consider groups of vertices in networks (cliques, plexes and cores) and transitivity (clustering coefficients, local clustering coefficients). Next, we will discuss the reciprocity, signed networks and structural balance in networks, in particular, we will present Harary's theorem on the balanced networks that states that all balanced networks are clusterable. Finally, we will discuss partitioning and community detection problems in networks and Kernighan-Lin algorithm for the network bisection problem.

    • The Large-Scale Structure of Networks and Network Models

      In this section we discuss important features of complex networks and network models. We first consider component sizes (giant component), path lengths and the small-world effect, degree distributions and power laws, scale-free networks. Next, we will discuss the different network models. Finally, we will consider the following network models in details: random graphs, configuration model, preferential attachment model, model of Barabasi and Albert, and small-world model.