Networks: Lecture 2IntroductionGraphsProperties of Networks6.207/14.15: Networks Lecture 2: Graph Theory and Social Networks Daron Acemoglu and Asu Ozdaglar MIT September 14, 2009 1Networks: Lecture 2 Introduction Outline Types of networks Graphs: notation and terminology Properties of networks: Diameter, average path length, clustering, degree distributions, centrality Reading: Jackson, Chapters 2 and 3 EK, Chapters 2 and 13 2Networks: Lecture 2 Introduction Networks in the Real World A network is a set of items (nodes or vertices) connected by edges or links. Systems taking the form of networks abound in the world. Types of Networks: Social and economic networks: A set of people or groups of people with some pattern of contacts or interactions between them. Facebook, friendship networks, business relations between companies, intermarriages between families, labor markets Questions: Degree of connectedness, homophily, small-world effects Information networks: Connections of “information” objects. Network of citations between academic papers, World Wide Web (network of Web pages containing information with links from one page to other), semantic (how words or concepts link to each other) Questions: Ranking, navigation 3Networks: Lecture 2 Introduction Networks in the Real World (Continued) Types of Networks: Technological networks: Designed typically for distribution of a commodity or service. Infrastructure networks: e.g., Internet (connections of routers or administrative domains), power grid, transportation networks (road, rail, airline, mail) Temporary networks: e.g., ad hoc communication networks, sensor networks, autonomous vehicles Questions: Does network structure support performance? Fragility? Cascading failures? Biological networks: A number of biological systems can also be represented as networks. Food web, protein interaction network, network of metabolic pathways 4Networks: Lecture 2 Introduction Network Study Historical study of networks: Mathematical graph theory: One of the pillars of discrete mathematics Started with Euler’s celebrated 1735 solution of the K o¨ nigsberg bridge problem. Networks also studied extensively in sociology. Typical studies involve circulation of questionnaires, leading to small networks of interactions. Recent years witnessed a substantial change in network research. From analysis of single small graphs (10-100 nodes) to statistical properties of large scale networks (million-billion nodes). Motivated by availability of computers and computer networks that allow us to gather and analyze large scale data. New Analytical Approach: Find statistical properties that characterize the structure of these networks and ways to measure them Create models of networks Predict behavior of networks on the basis of measured structural properties and models 5Networks: Lecture 2 Graphs Graphs—1 We represent a network by a graph (N, g ), which consists of a set of nodes N = {1, . . . , n} and an n × n matrix g = [gij ]i,j∈N (referred to as an adjacency matrix), where gij ∈ {0, 1} represents the availability of an edge from node i to node j. The edge weight gij > 0 can also take on non-binary values, representing the intensity of the interaction, in which case we refer to (N, g ) as a weighted graph. We refer to a graph as a directed graph (or digraph) if gij �= gji and an undirected graph if gij = gji for all i, j ∈ N. ⎡ ⎤ 0 1 0 Example 1: ⎣ 0 0 1 ⎦ ⇒1 0 0 1 2 3 ⇒ 1 1 ⎡ ⎤ 0 1 1 Example 2: ⎣ 1 0 1 ⎦ ⇒1 1 0 2 3 2 3 6� � Networks: Lecture 2 Graphs Graphs—2 Another representation of a graph is given by (N, E ), where E is the set of edges in the network. For directed graphs: E is the set of “directed” edges, i.e., ( i , j ) ∈ E . For undirected graphs: E is the set of “undirected” edges, i.e., {i, j} ∈ E . In Example 1, Ed = {(1, 2), (2, 3), (3, 1)} In Example 2, Eu = {1, 2}, {1, 3}, {2, 3} When are directed/undirected graphs applicable? Citation networks: directed Friendship networks: undirected We will use the terms network and graph interchangeably. We will sometimes use the notation (i, j ) ∈ g (or {i , j } ∈ g) to denote gij = 1. 7Networks: Lecture 2 Graphs Walks, Paths, and Cycles—1 We consider “sequences of edges” to capture indirect interactions. For an undirected graph (N, g ): A walk is a sequence of edges {i1, i2}, {i2, i3}, . . . , {iK −1, iK }. A path between nodes i and j is a sequence of edges {i1, i2}, {i2, i3}, . . . , {iK −1, iK } such that i1 = i and iK = j, and each node in the sequence i1, . . . , iK is distinct. A cycle is a path with a final edge to the initial node. A geodesic between nodes i and j is a “shortest path” (i.e., with minimum number of edges) between these nodes. A path is a walk where there are no repeated nodes. The length of a walk (or a path) is the number of edges on that walk (or path). For directed graphs, the same definitions hold with directed edges (in which case we say “a path from node i to node j”). 8Networks: Lecture 2 Graphs Walks, Paths, and Cycles—2 i j i j i j i j walk path between i and j cycle shortest path Note: Under the convention gii = 0, the matrix g2 tells us number of walks of length 2 between any two nodes: (g × g )ij = ∑k gik gkj Similarly, gk tells us number of walks of length k. 9Networks: Lecture 2 Graphs Connectivity and Components An undirected graph is connected if every two nodes in the network are connected by some path in the network. Components of a graph (or network) are the distinct maximally connected subgraphs. A directed graph is connected if the underlying undirected graph is connected (i.e., ignoring the directions of edges). strongly connected if each node can reach every other node by a “directed path”. 1 2 3 Figure: A directed graph that is connected but not strongly connected 10Networks: Lecture 2 Graphs Trees, Stars, Rings, Complete and Bipartite Graphs A tree is a connected (undirected) graph with no cycles. A connected graph is a tree if and only if it has n − 1 edges. In a tree, there is a unique path between any two nodes. Complete graph Ring Star Bipartite graph Tree actors movies 11Networks: Lecture 2 Graphs Neighborhood and Degree of a Node The neighborhood of node i is the set of nodes that i is connected to. For undirected graphs: The degree of node i is the number of edges that involve i (i.e.,