### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 696 Class Note for PHYS 597A with Professor Albert at PSU

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 32 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 20 views.

## Similar to Course at Penn State

## Reviews for 696 Class Note for PHYS 597A with Professor Albert at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Graph concepts Graphs are made up by vertices nodes and edges lanS An edge connects two vertices or a vertex with itself loop AC AC multiple edges BB loop The shape of the graph does not matter only the way the nodes are connected to each other Simple graph does not have loops selfedges and does not have multiple identical edges Further reading httpwwwutmedudepartmentsmathgraphglossaryhtml Symmetrical and directed graphs Two distinct types of edges symmetrical and directed also called arcs Two different graph frameworks graph digraph directed graph In the digraph framework a symmetrica edge means the superposiuuu of two opposite directed edges Node degrees Node degree the number of edges connected to the node 12 4 In directed networks we can de ne an in degree and outdegree The total degree is the sum of in and outdegree kg 2 kg I kc 3 Source a node with indegree 0 Sink a node with outdegree 0 Eg A F are sources B is a sink Average degree mega N the number of nodes in the graph OilquotFizzyquot ltk0mgt5i k u2 kingtltkamgt N l Ni1 I Q What is the relation between the number of edges in a nondirected graph and the sum of node degrees How about in a directed graph Statistics of node degrees Ox H Average degree 11 The degree distribution Pk gives the fraction of nodes that have k edges Similarly Pki Pk gives the fraction of nodes that have indegree kiquot outdegree km EX Calculate the degree distributions of the graphs in the left Paths and circuits Adjacent nodes vertices there is an edge joining them In the digraph framework the adjacency only defined in the direction of the arrow Path a sequence of nodes in which each node is adjacent to the next one Edges can be part ofa path only once In the digraph framework a symmetrical edge can be used once in one direction and once in the opposite direction Circuit a path that starts and ends at the same Ex Give examples vertex of circuits and cycles in the above graph Cycle a circuit that does not revisit any nodes Connectivity of undirected graphs Connected undirected graph any two vertices can be joined by a path Adisconnected ra h is made u b two or more connected com onents B B A A D c D C E E F F G G Bridge if we erase it the graph becomes disconnected Connectivity of directed graphs Stroneg connected directed graph has a path from each node to every other node and vice versa eg AB path and BA path Weakly connected directed graph it is connected if we disregard the edge directions Stroneg connected components can be identified but not every node is part OT a nOnII39IVIaI strongly connected component B ncomponent nodes that can reach the scc outcomponent nodes that can be reached from the scc Exercises 1 Draw a graph or digraph with 4 nodes such that each node has degree 1 2 3 Try to use a variety of edges symmetrical directed multiple edges loops 2 You have N nodes and need to build a connected graph from them Each time you add an edge you must pay 1 What is the minimum amount of money needed to build the graph 3 You are constructing a disconnected graph from N nodes For each edge you add you receive 1 You are not allowed to use directed edges loops or multiple edges and you must stop before the graph becomes connected What is the most money you can make Exercise the bridges of Konigsberg Walking problem traverse each bridge do not recross any bridge return to the starting point Euler circuit return to the starting Emit 3926le point by traveling each edge of the 4 39 graph once and only once Is there a solution to the Konigsberg bridge walking problem Euler s theorem a If a graph has any vertices of odd degree it cannot have an Euler circuit b If a graph is connected and every vertex has an even degree it has at least one Euler circuit How would we need to modify the graph so it has an Euler circuit Euler circuits in directed graphs If a divra h is stronvl connected and the indegree of each node is equal to its out degree then there is an Euler circuit Q Give one possible Euler circuit Otherwise there is no Euler circuit This is because in a circuit we need to enter each node as many times as we leave it Distances between nodes B A D L B A D t The distance between two nodes is defined as the number of edges along the shortest path connecting them Ifthe two nodes are disconnected the distance is infinity In digraphs each path needs to follow the ir i n f h Thus in a digraph the distance from node A to lTW B on an AB path is generally different from the distance from node B toA on a BA path Ex Calculate the distances among node pairs for the above graphs How to record distances ABCD A quot AB AC AD Tip fill out the matrix B IBA lac IBD C CA CB quot ICD D IDA DB IDC 39 Q How many entries will you need for an N node graph A NN1 in a digraph NN12 in a symmetrical graph Let s use the notation N NN1 N airs 1 2 2 Diameter and average distance Graph diameter the maximum distance between any pair of nodes in the graph Note not the longest path Average path lengthdistance for a connected graph component or a strongly connected component of a digraph 1 where l is the distance from node ito node ltzgt 2a a ZNPWS 73quot j N N m and N is the pairs 2 2 number of nodes in the graph or component Since in a symmetrical graph IU lj we only need to count them once lt1 E N Z 1 pairs I39dgt1 Algorithm for finding distances breadth first search Distance between node u and node v 1 2 3 Ulrb Start at u Find the nodes adjacent to u Mark them as at distance at them in a queue Take the first node w out ofthe queue Find the unmarked nodes ad acent to it in the gra h Mark them with the label ofw 1 Put them in the queue Repeat until you find v or there are no more nodes in the queue The distance between u and v is the label of v or if v does not have a label infinity A B 1 Ex Apply the algorithm to find the F 1 Q3 distance between A and C E z D 2 Other applications of breadth first search Find the connected components of a graph Start from a node u label with 1 Find all nodes reachable from u label with 1 Choose an unmarked node v label with 2 Find all nodes reachable from v label with 2 Repeat with increasing labels until no more unmarked nodes P PWNT Calculate average distance of a connected graph 1 Put the nodes in an ordered list 2 Use BFS to find distances between the first node and all other nodes cumulate them 3 Use BFS to find distance ween e H d l ot nodes except the first cumulate them 4 Repeat as you go down the list 5 Divide cumulated distance b the number of node airs Note that BFS can only find the reachable nodes Graph efficiency To avoid infinities in graphs that are not connected and digraphs that are not strongly connected one can define a graph etriciency average inverse distance 7 1 2i A B ZNFM Wmly Npairs istne number or node pairs D C Ex Calculate the average distance and efficiency ofthe graphs on the right B Betweenness centralitd loadl For all node pairs 1 j Find all the shortest paths between nodes i and j Ci Determine how many of these pass through node k C k The betweenness centrality of node k is Ckij amp Cm L C Freeman Sociometry 40 35 1977 A C i i B gk 2 z k isj C0 F CiJ inr of shortest paths btw i Ck J 7 nr of these paths that contain k 11x1 paicuiare Lne betweenness centrality or The nodes in this grapn Do not count being the starting or ending point of a path k 139 19739 Tip Construct a node pair haliumx mm m u wiLu me uouw between each node pair EX2 Determine the betweenness centralitJ distribution for the Ural h Common subgraphs Subgraph a subset of nodes of the original graph and of edges connecting them Does not have to contain all the edges of a node included in the subgraph Trees contain no circuits N nodes and N1 edges m Ocles circuits where nodes are not revisited A II N nodes and N edges 8 Q cliques completely connected suograpns N nodes and NN 12 edges E Note difference between connected and completely connected Special directed subgraphs X Y Bifan D g I Z W X Feedforwar nintersecting i directed paths between a start and endpoint T Z Biparallel two nonintersectin paths of identical Ien th X between a start and endpoint M amp Y Z Ax Z ieedback loop a directed cycle xv W 2 9w S Shen Orr R IVIilot S Mangan and U Alon Nature Genetics 2002 Network topology and dynamics Network motifs can illustrate regulatory relationships m linear pamway I lk branching point quotquot55 quot WWW feulrl39m39wanl loop 1 05 jve negative quot11le 1001 feedback loop Further dynamic details are needed to describe how multiple inputs on a node are integrated additive action e g same product for two chemical reactions synergy eg transcriptional regulation Weighted networks In some applications it is necessary quantify edges with weights corresponding eg to a traversal cost or a geographical distance Then the shortest path between two nodes is redefined in terms of weight eg the path with lowest cost or most efficient path Io find the distance between two nodes In a weighted network calculate the sum of edge weights on each path this is the path weight then select the path with lowest weight where is the path w imum weight wUis the weight of edge ij Kruskal s algorithm to find the minimum spanning tree or a graph MS a tree that contains all nodes of the graph and as minimal edge weight I iiI11II1 FM H HMEMU 7 quotinquot 1 I FL I II 39 1391 12 3 l Litthink k g 391 7quot Frulul quotw 39 21 i r iquot flittllli lintlgl 7393 391 ILIEFIEE IIII Find the cheapest edge in the graph and marK It Continue selecting the cheapest remaining edge at each step but do not select edges that create circuits When the number of edges is one less than the number of vertices STOP Bipartite graphs Group structure eg in social networks can be incorporated into a bipartite grap A bipartite graph has two types of nodes group nodes black numbered member nodes white lettered Edges are possible only between different types of nodes membership in group An alternative representation connects all members in a given group each group becomes a completely connected subgraph D Watts P S Dodds M E J Newman Science 296 2002 M E J Newman 8 Strogatz D Watts Phys Rev E 64 026118 2001 Local order and clustering Cliques completely connected subgraphs kN 1nN 1 How close the neighborhood of a node is to a W Clique Edges among first neighbors of node i n Clustering coefficient C 5 1 k 01 or I klkl 12 l C nr of triangles connected to i nr 0f triples centered on i Q How would you generalize the concept of clustering coefficient to directed graphs Cumulating clustering coefficients 3 0 0 C L k a 01 nr of triangles connected to i 39 kiki 12 j LL Ci I v nr 0f triples centered 0n 1 1 N Average clustering coeffICIent 5 20 N i1 1 Clustering degree function Ck for each degree represented in the graph calculate the average clustering coefficient of the nodes with that degree Ex Determine the average clustering coefficient clustering distribution and clusteringdegree function of the above graph EX 1 N nodes are connected by N edges such that they form a cycle This is also called a ring latt1ce How does the maximum distance between nodes the diameter depend on N How about the average distance EX 2 On the ring lattice i m bove VJ es m ighbor is connected by an edge What is the clustering coef cient of the nodes EX 3 Construct a square lattice grid L edges long How does the maximum distance between nodes depend on L Regular lattices ex 1 1D lattice ring W W k 4 for each node Cgfor each nodeif N gt 6 If N In N IZ4N gt lmss ltlgt gt ltlgt 1 4 N 8 The average pathlength varies as lt l gtN N Constant degree constant clustering coefficient Clustering coefficient of 1D lattice Ngt12 the origin black node is connected to 4 nodes on each side Edges among neighbors I 6 5 4 3 18 9 firSt Bighbors second neighbors C on lattice 14 I C3k 1 h 2k39thd f hd n enera w ere Is e e reeo eac no e g 2 2k 1 g and Ngt3k kgt1 Regular lattices ex 2 2D lattice k 6 for inside nodes C i for inside nodes 15 l 1 61N 21quot ch 1 ltlgtLN1Z In general the average distance varies as lt l gt NJ where D is the dimensionalit39 of the lattice Constant degree coordination number constant clustering coefficient Regular lattices ex 3 the Cayley tree k 3 for inside nodes g lt k gt 2 4 k I for surface nodes C 0 1mm 13ZZHN twee ng H logltkgt l N ltlgt L logltkgt Distances vary logarithmically with N Constant degree no clustering

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.