### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Department

This 30 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 14 views.

## Similar to Course at Penn State

## Reviews for 556 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 links 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 In the digraph framework a symmetrical edge means the superposition of two opposite directed edges Node degrees Node degree the number of edges connected to the node ki 4 n 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 N ltkmgta zkza ltkmgta zkruz ltkmgtltwgt i1 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 WM 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 ki 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 of a path only once A path in a directed network needs to follow the direction of the edges thus a symmetrical edge in the digraph framework can be used once in one direction and once in the opposite Ex Give examples Circuit of circuits in the a path that starts and ends at the same vertex above graph Connected and disconnected graphs Connected graph any two vertices can be joined by a path A disconnected graph is made up by connected components B B A A D c D c E E F bF 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 of a nontrivial strongly connected component B ncomponent nodesthat 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 a ight nk traverse each bridge l 39 f quot3 do not recross an br39d ma ac5 39 y I ge a 1 if islamif return to the starting point 4quot W1quot 39 i ll 45 quot quotEmmi Euler circuit return to the starting ix tfmk Aim point by traveling each edge of the i ii 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 Euler circuits in directed graphs If a digraph is strongly connected and the indegree of each node is equal to its out degree then there is an Euler circuit C I E Q Give one possible Euler circuit OthenNise 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 The distance between two nodes is defined B A as the number of edges along the shortest path connecting them D C If the two nodes are disconnected the distance is infinity In digraphs each path needs to follow the B direction ofthe arrows Thus in a digraph the distance from node A to B on an AB path is generally different from the distance from node B to A on a BA path EX Calculate the distances among node pairs for the above graphs How to record distances Tip fill out the matrix 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 W 1 Z where I is the distance from node ito node 2N N NN l pairs I39dil 2 2 jand NW Since in a symmetrical graph IU ljy we only need to count them 1 once lt1 E N Z 1 pairs I39dgt1 Graph efficiency To avoid infinities in graphs that are not strongly connected one can define a graph efficiency average inverse distance 1 1 21v 211 B pairs Ma y A 77 N is the number of node pairs paii S Ex Calculate the average distance and efficiency of the graphs on the right B Betweenness centrality load Find all the shortest paths between nodes i and j Ci Determine how many of these pass through node k Ck y The betweenness centrality of node k is Ck 13139 amp39Cmn L C Freeman Sociometry 40 35 1977 C i 39 B gk 2 2 11 isj Clal F C CiJ inr of shortest paths btw i Ck d 7 nr ofthese paths that contain k Exl Calculate the betweenness centrality of the nodes in this graph Do not count being the starting or ending point of a path km kzj39 Tip Construct a node pair halfmatrix and fill it with the nodes between each node pair EX2 Determine the betweenness centrality distribution for the graph Common subgraphs Subgraph a subset ofnodes of the original graph and of edges connecting them Does not have to contain all the edges ofa node included in the subgraph Trees contain no circuits N nodes and N1 edges m Cycles circuits where nodes are not revisited A II N nodes and N edges 8 Q Cliques completely connected subgraphs N nodes and NN12 edges E Special directed subgraphs X Y Bifan I Z W X Feedforwar I nintersecting l directed paths between a start and endpoint T Z Biparallel two nonintersecting paths of identical length X between a start and endpoint M amp Y Z N M Feedback loop a directed cycle W Z W S S ShahUrn R Nilltl S Mungan and U Alon Nature GCHEIICS ZUOZ Network topology and dynamics Network motifs can illustrate regulatory relationships m linear pamway I lk branching paint quotquot55 quot WWW feulrl39m39wanl loop 1 05 jve negative Wthk 1001 feedback 10on Further dynamic details are needed to describe how multiple inputs on a node are integrated additive action eg 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 To 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 1 2 wk wk wmj where i k Imj is the path with minimum weight wjis the weight of edge ij Kruskal s algorithm to find the minimum spanning tree of a graph Find the cheapest edge in the graph l2imln z 39 H a 339 LL 39 IL and mark It lLiL39C I 53quot H 39 quot 3 439 n Continue selecting the cheapest V p quot4 remaining edge at each step but do not 3 Ug lllL39d L 51 l 391 my select edges that create circuits It When the number of edges is one less Allle ll ldl 394 39l39iuimim than the number of vertices STOP Ex Delete the three highestweight edges from the graph Find the weighted distances between the nodes in the modified graph Bipartite graphs Group structure eg in social networks can be incorporated into a bipartite graph 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 k N n m g 2 gt How close the neighborhood of a node is to a clique Edges among first neighbors of node i Clustering coefficient n C 5 1 kl 01 or klkl 12 C nr of triangles connected to i l nr 0f triples centered on i Cumulating clustering coefficients 3 0 0 C L k a 01 nr of triangles connected to i 39 kiki I2 j LL Ci I v nr 0f triples centered 0n 1 K I I N 39 Average clustering coefficient 5 C I Clustering degree function Ck for each degree represented in the graph calculate the average clustering coefficient ofthe nodes with that degree Ex Determine the average clustering coefficient clustering distribution and clusteringdegree function ofthe above graph EX 1 N nodes are connected by N edges such that they form a cycle This is also called a ring lattice How does the maximum distance between nodes the diameter depend on N How about the average distance EX 2 On the ring lattice om above every second neighbor 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 inside nodes C g for inside nodes if N m N 124N lmz ltlgt gt ltlgt 1 4 N 8 The average pathlength varies as lt l gt93 N Constant degree constant clustering coefficient Clustering coefficient of 1D lattice The origin black node is connected to k 4 nodes on each side Total possible edges among neighbors 2k2k 12 Enumerate edges that are actually there n2k 22k 1 22k 2 2 2k i 1 2 k 1 First neighbors second neighbors edge length on lattice kth neighbors k 2 2k 1 39 C vi 1H 2k2k 1 22k 1 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 1 gt13 NJ where D is the dimensionality 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 1322HN 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.