WIXLIB

Introduction to NetworkTheory

What is a Network? Network graph Informally a graph is a set of nodes joined by a set of lines orarrows.123456123456

Graph-based representations Representing a problem as a graph canprovide a different point of viewRepresenting a problem as a graph canmake a problem much simpler More accurately, it can provide theappropriate tools for solving the problem

What is network theory? Network theory provides a set oftechniques for analysing graphsComplex systems network theory providestechniques for analysing structure in asystem of interacting agents, representedas a networkApplying network theory to a systemmeans using a graph-theoreticrepresentation

What makes a problem graph-like? There are two components to a graph In graph-like problems, these componentshave natural correspondences to problemelements Nodes and edgesEntities are nodes and interactions betweenentities are edgesMost complex systems are graph-like

Friendship Network

Scientific collaboration network

Business ties in US biotechindustry

Genetic interaction network

Protein-Protein InteractionNetworks

Transportation Networks

Internet

Ecological Networks

Graph Theory - HistoryLeonhard Euler's paper on “SevenBridges of Königsberg” ,published in 1736.

Graph Theory - HistoryCycles in PolyhedraThomas P. KirkmanWilliam R. HamiltonHamiltonian cycles in Platonic graphs

Graph Theory - HistoryTrees in Electric CircuitsGustav Kirchhoff

Graph Theory - HistoryEnumeration of Chemical IsomersArthur CayleyJames J. SylvesterGeorge Polya

Graph Theory - HistoryFour Colors of MapsFrancis Guthrie Auguste DeMorgan

Definition: Graph G is an ordered triple G: (V, E, f) V is a set of nodes, points, or vertices.E is a set, whose elements are known as edges or lines.f is a function maps each element of E to an unordered pair of vertices in V.

Definitions Vertex Basic ElementDrawn as a node or a dot.Vertex set of G is usually denoted by V(G), or VEdge A set of two elementsDrawn as a line connecting two vertices, called end vertices, orendpoints.The edge set of G is usually denoted by E(G), or E.

Example V: {1,2,3,4,5,6} E: {{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

Simple GraphsSimple graphs are graphs without multiple edges or self-loops.

Directed Graph (digraph) Edges have directions An edge is an ordered pair of nodesloopmultiple arcarcnode

Weighted graphs is a graph for which each edge has an associated weight, usuallygiven by a weight function w: E R.11.223.2.3.541.55.516225143536

Structures and structuralmetrics Graph structures are used to isolateinteresting or important sections of agraphStructural metrics provide a measurementof a structural property of a graph Global metrics refer to a whole graphLocal metrics refer to a single node in a graph

Graph structures Identify interesting sections of a graph Interesting because they form a significantdomain-specific structure, or because theysignificantly contribute to graph propertiesA subset of the nodes and edges in agraph that possess certain characteristics,or relate to each other in particular ways

Connectivity a graph is connected if you can get from any node to any other by following a sequence of edgesORany two nodes are connected by a path.A directed graph is strongly connected if there is a directed path fromany node to any other node.

Component Every disconnected graph can be split up into a number ofconnected components.

Degree Number of edges incident on a nodeThe degree of 5 is 3

Degree (Directed Graphs) In-degree: Number of edges entering Out-degree: Number of edges leaving Degree indeg outdegoutdeg(1) 2indeg(1) 0outdeg(2) 2indeg(2) 2outdeg(3) 1indeg(3) 4

Degree: Simple Facts If G is a graph with m edges, thenΣ deg(v) 2m 2 E If G is a digraph thenΣ indeg(v) Σ outdeg(v) E Number of Odd degree Nodes is even

WalksA walk of length k in a graph is a succession of k(not necessarily different) edges of the formuv,vw,wx, ,yz.This walk is denote by uvwx xz, and is referred toas a walk between u and z.A walk is closed is u z.

Path A path is a walk in which all the edges and all the nodes are different.Walks and Paths1,2,5,2,3,41,2,5,2,3,2,1walk of length 5CW of length 61,2,3,4,6path of length 4

Cycle A cycle is a closed path in which all the edges are different.1,2,5,13-cycle2,3,4,5,24-cycle

Special Types of Graphs Empty Graph / Edgeless graph No edgeNull graph No nodesObviously no edge

Trees Connected Acyclic Graph Two nodes have exactly one pathbetween them

Special TreesPathsStars

RegularConnected GraphAll nodes have the samedegree

Special Regular Graphs: CyclesC3C4C5

Bipartite graph V can be partitioned into 2 sets V1and V2such that (u,v) E implies either u V1 and v V2OR v V1 and u V2.

Complete Graph Every pair of vertices are adjacent Has n(n-1)/2 edges

Complete Bipartite Graph Bipartite Variation of Complete Graph Every node of one set is connected to every other node on theother setStars

Planar Graphs Can be drawn on a plane such that no two edges intersect K4 is the largest complete graph that is planar

Subgraph Vertex and edge sets are subsets of those of G a supergraph of a graph G is a graph that contains G as asubgraph.

Special Subgraphs: CliquesA clique is a maximum completeconnected subgraph.ABCDEFGHI

Spanning subgraph Subgraph H has the same vertex set as G. Possibly not all the edges“H spans G”.

Spanning tree Let G be a connected graph. Then aspanning tree in G is a subgraph of Gthat includes every node and is also atree.

Isomorphism Bijection, i.e., a one-to-one mapping:f : V(G) - V(H)u and v from G are adjacent if and only if f(u) and f(v) areadjacent in H. If an isomorphism can be constructed between two graphs, thenwe say those graphs are isomorphic.

Isomorphism Problem Determining whether two graphs areisomorphic Although these graphs look very different,they are isomorphic; one isomorphismbetween them isf(a) 1 f(b) 6 f(c) 8 f(d) 3f(g) 5 f(h) 2 f(i) 4 f(j) 7

Representation (Matrix) Incidence Matrix VxE[vertex, edges] contains the edge's dataAdjacency Matrix VxVBoolean values (adjacent or not)Or Edge Weights

Matrices1234561,2 1,5 2,3 2,5 3,4 4,5 4,61 1000001 0110000 0101000 015 1 1 0 1 0 06 0 0 0 1 0 001

Representation (List) Edge List pairs (ordered if directed) of verticesOptionally weight and other dataAdjacency List (node list)

Implementation of a Graph. Adjacency-list representation an array of V lists, one for each vertex in V.For each u V , ADJ [ u ] points to all its adjacent vertices.

Edge and Node ListsEdge List121223253343455354Node List12223533435534

Edge Lists for WeightedGraphsEdge List1 2 1.22 4 0.24 5 0.34 1 0.55 4 0.56 3 1.5

Topological DistanceA shortest path is the minimum pathconnecting two nodes.The number of edges in the shortest pathconnecting p and q is the topologicaldistance between these two nodes, dp,q

Distance Matrix V x V matrix D ( dij ) such thatdij is the topological distance between i and j.123456101221321012133210122422101151121026332120

N 12Random GraphsErdős and Renyi (1959)p 0.0 ; k 0N nodesA pair of nodes has probability p ofbeing connected.Average degree, k pNp 0.09 ; k 1What interesting things can be said fordifferent values of p or k ?(that are true as N )p 1.0 ; k ½N2

Random GraphsErdős and Renyi (1959)p 0.0 ; k 0p 0.09 ; k 1p 0.045 ; k 0.5Let’s look at Size of the largest connected clusterp 1.0 ; k ½N2Diameter (maximum path length between nodes) of the largest clusterAverage path length between nodes (if a path exists)

Random GraphsErdős and Renyi (1959)p 0.0 ; k 0p 0.045 ; k 0.5p 0.09 ; k 1p 1.0 ; k ½N2511124712.04.21.0Size of largest component1Diameter of largest component0Average path length between nodes0.0

Random GraphsIf k 1: small, isolated clusterssmall diametersshort path lengthsAt k 1: a giant component appearsdiameter peakspath lengths are highFor k 1: almost all nodes connecteddiameter shrinkspath lengths shortenPercentage of nodes in largest componentDiameter of largest component (not to scale)Erdős and Renyi (1959)1.001.0phase transitionk

Random GraphsErdős and Renyi amaWhat does this mean? If connections between people can be modeled as a random graph, then then Because the average person easily knows more than one person (k 1), We live in a “small world”world” where within a few links, we are connected to anyone in the world. ErdőErdős and Renyi showed that averagepath length between connected nodes is

Random GraphsErdős and Renyi (1959)DavidMumfordFanChungWhat does this mean? PeterBelhumeurKentaroToyamaBIG “IF”!!!If connections between people can be modeled as a random graph, then then Because the average person easily knows more than one person (k 1), We live in a “small world”world” where within a few links, we are connected to anyone in the world. ErdőErdős and Renyi computed averagepath length between connected nodes to be:

The Alpha ModelWatts (1999)The people you know arenʼarenʼt randomly chosen.People tend to get to know those who are twolinks away (Rapoport(Rapoport *, 1957).The real world exhibits a lot of clustering.The Personal Mapby MSR Redmond’s Social Computing Group* Same Anatol Rapoport, known for TIT FOR TAT!

The Alpha ModelWatts (1999)α model: Add edges to nodes, as in randomgraphs, but makes links more likely whentwo nodes have a common friend.For a range of α values:Probability of linkage as a functionof number of mutual friends(α is 0 in upper left,1 in diagonal,and in bottom right curves.) The world is small (average path length isshort), and Groups tend to form (high clusteringcoefficient).

The Alpha ModelWatts (1999)Clustering coefficient /Normalized path lengthα model: Add edges to nodes, as in randomgraphs, but makes links more likely whentwo nodes have a common friend.For a range of α values: The world is small (average path length isshort), and Groups tend to form (high clusteringcoefficient).Clustering coefficient (C) andaverage path length (L)plotted against αα

The Beta ModelWatts and Strogatz (1998)β 0β 0.125β 1People knowtheir neighbors.People knowtheir neighbors,and a few distant people.People knowothers atrandom.Clustered, butnot a “small world”Clustered and“small world”Not clustered,but “small world”

The Beta ModelWatts and Strogatz h α and β models reproduce short-path resultsof random graphs, but also allow for clustering.Small-world phenomena occur at thresholdbetween order and chaos.Clustering coefficient /Normalized path lengthFirst five random links reduce the average pathlength of the network by half, regardless of N!Clustering coefficient (C) and averagepath length (L) plotted against β

Power LawsAlbert and Barabasi (1999)WhatʼWhatʼs the degree (number of edges) distributionover a graph, for real-world graphs?Random-graph model results in Poissondistribution.But, many real-world networks exhibit a power-lawdistribution.Degree distribution of a random graph,N 10,000 p 0.0015 k 15.(Curve is a Poisson curve, for comparison.)

Power LawsAlbert and Barabasi (1999)WhatʼWhatʼs the degree (number of edges) distributionover a graph, for real-world graphs?Random-graph model results in Poissondistribution.But, many real-world networks exhibit a power-lawdistribution.Typical shape of a power-law distribution.

Power LawsAlbert and Barabasi (1999)Power-law distributions are straight lines in log-logspace.How should random graphs be generated to createa power-law distribution of node degrees?Hint:ParetoʼParetoʼs* Law: Wealth distribution follows apower law.Power laws in real networks:(a) WWW hyperlinks(b) co-starring in movies(c) co-authorship of physicists(d) co-authorship of neuroscientists* Same Velfredo Pareto, who defined Pareto optimality in game theory.

Power LawsAnandanAlbert and Barabasi (1999)JenniferChayesKentaroToyama“The rich get richer!”richer!”Power-law distribution of node distribution arises if Number of nodes grow;Edges are added in proportion to the number of edgesa node already has.Additional variable fitness coefficient allows for somenodes to grow faster than others.“Map of the Internet” poster