### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Molecular Modeling BINF 739

Mason

GPA 3.64

### View Full Document

## 28

## 0

## Popular in Course

## Popular in BioInformatics

This 133 page Class Notes was uploaded by Nathanael Schowalter on Monday September 28, 2015. The Class Notes belongs to BINF 739 at George Mason University taught by Jeffrey Solka in Fall. Since its upload, it has received 28 views. For similar materials see /class/215253/binf-739-george-mason-university in BioInformatics at George Mason University.

## Reviews for Molecular Modeling

### 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: 09/28/15

Introduction to Graph Models BINl739 SPRING2007 Jeff Solka and Jennifer Weller Introduction to Graph Models BINF739 SolkaWeller BINF739 Acknowledgement Unless otherwise noted all figures in this lecture have been adapted from Gross and Yellen Graph 777603 anthsAppica on Chapman and HallCRC Press 2006 Introduction to Graph Models BINF739 SolkaWeller BINF739 What is a Graph A graph consists of a collection of nodes and edges that connect the nodes The nodes are entities and the edges represent relationships between the entities Nodes proteins in a cell Edges relationships between these proteins Usually denoted G V E l vertices and E edges Edges can of course be assigned weights directions and types Introduction to Graph Models BINF739 SolkaWeller BINF739 Applications of Graph Theory Communication networks Social network analysis Regulatory and developmental networks Citation networks Statistical data mining Dimensionality reduction Classification Clustering Introduction to Graph Models BINF739 SolkaWeller BINF739 Practicalities We are often provided with imperfect data There can be errors in our edge assignments False positive relationships that appear between two nodes that are not actually there False negative relationships that are real but were not experimentally detected Untested relationships there could be a relationship here but there was no data to test said relations ip There may olten be uncertainty associated with the edges Uncertainty between two graphs may merely be related to the fact that in the second graph the nodes had been more extensively studied Introduction to Graph Models BINF739 SolkaWeller BINF739 Representations of Graphs Graphs can have various representations and depending on the algorithm that we are implementing one representation may be more fortuitous than another Edge list Adjacency matrix From to matrices Introduction to Graph Models BINF739 SolkaWeller BINF739 Graphs and Data Analysis Knowledge Representation Metabolic and signal transduction networks Gene Ontology GO Bipartite graphs between genes and scientific papers that cite the genes Exploratory Data Analysis Mapping of gene ex ression data onto static knowledge representation grap s Statistical Inference Two genes are related due to frequent cocitation or that gene expression is related to protein complex comembership Random graphs such as ErdosReyni as well as simulation graphs that involve node permutations Introduction to Graph Models BINl739 SolkaWeller BINH39 Glycan Pathway as Provided by KEGG Irish1mm m quotWm Nmynmm NClymxkgmhn m NGlycanbimynlhum oGiymbmmm l Pepimchyquotnr mymmiu mm mum hmmmms cl mm n m yam Pquot P DGlmmnin and Dammm nclnbclivn CLnnJroihi imam vaummma mm Lviusyiilhaix bivaymlni mama wwwqu v 39ammgiympm hian lnmscne I I I I Bkmmw wm www risannmsI I nif himynlhcx n nmlulnmies f Introduction to Graph Models BINl739 SolkaWeller BINH39 Gene Ontology A Graph of Concept Terms Figma 11 Limp ul UO yrim Eulbllipi far xlio hi m quotI rmwxrimimi Enrxtur mi ivixv Gentleman et al Bionformatics and Computational Biology Solutions Using R and Bjoconducfof Springer 2005 Introduction to Graph Models BINF739 SolkaWeller BINF739 Bipartite Gene Article Graph mam A vmmsiaill mm quot F i mums i t i l Wiw CW Flume Hui A liipdrlile manly hemp qai39iinm will quotllquot and ii39iii lzu ll nlile it iLmultLiuk lemme will 39linw mm Hurling mm quotmm Gentleman et al Bionformatics and Computational Biology Solutions Usng R and Bioconducton Springer 2005 Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Graphs and Digraphs Def A graph G E is a mathematical structure consisting of two finite sets land E The elements of l are called the vertices or nodes and the elements of E are called the edges Each edge has a set of one or two vertices associated with it which are called its endpoints k F a v A I a D 0 I a a mum Linn Inwing a graph ms 1 gm u Ex 111 The vertex and edge set of graph A is VA p q r 5 and a 17 pr 5 r5 175 Ex 111 The 0 en nei hborhood ofa vertex Vin a graph G denoted IlV is the set of all the neighbors of v The closed neighborhood of v is given by IlV IlV U V Inn39oduction to Graph Models BIN F739 SolkaWeller BIN F739 11 Simple Graphs and General Graphs Def A proper edge joins two distinct vertices Def A selfloop is an edge thatjoins a single endpoint to itself Def A multiedge is a collection of two or more edges having identical endpoints The edge multiplicity is the number of edges within the multiedge Def A simple graph has neither selfloops nor multiedges Def A loopless graph or multigraph may have multiedges but no selfloops Def A general graph may have selfloops andor multi edges Inn39oduction to Graph Models BIN F739 SolkaWeller BIN F739 11 Null and Trivial Graphs Def A null graph is a graph whose vertex and edgesets are empty Def A trivial graph is a graph consisting of one vertex and no edges Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Edge Directions Def A directed edge or arc is an edge one of whose endpoints is designated as the tail and whose other endpoint is designated as the head Def A directed graph or a digraph is a graph each of whose edges is directed A digraph is simple if it has neither selfloops or multiarcs Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Edge Directions Exaulplt 1112 Ilu illEl filJll in I mnr I l 2 in mnlvln lis m lurk w ill in Figure112 A simple digraph with a pair or uppnsih39ly diremu 11m Bmxpln 1181 Hm digraph I In Hpr LII 1w Ihn graph 39139 u in mum2 graph I 1 Hull 115 A dippa mm in undying vnph Introduction to Graph Models BINF739 SolkaWeller BINF739 1 1 Formal Specifications of Graphs and Dig raphs Def A formal specification of a simple graph is given by an adjacency table with a row for each vertex containing the list of neighbors of that vertex 9 Q mgr qtpa my IIIqu A l Flum 111 A nhnpla guph and ll banal pael eullnn Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Formal Specifications of Graphs and Digraphs Def A formal s ecification of a eneral ra h G l E endpts consists of a list of its vertices a list of its edges and a tworow incidence table specifying the endpts function whose columns are indexed by its edges The entries in the column corresponding to edge e are the endpoints of e The same endpoint appears twice if e is a selfloop 1 rim in luridnil iiilluq l 39l ll 1 39l i l l in iviiiiu w Figure 115 A giruvml graph and ifs urinalgt13939i t39zlliuli Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Formal Specifications of Graphs and Digraphs Def A formal specification of a general digraph or a mixed graph D l E endpts head tail is obtained from the formal specifications of the underlying graph by adding the functions head EG amp lGand tail EG amp 0 which designate the head vertex and tail vertex of each arc himlul lufllul llilllll il fillHi7 NHLHI iriilli i ll limim hrm ii himm infW mull i mill l v Imidlyi lilllIl Millll liulvll u Figure116 A gmwrul digraph and Alumnid1 Sprd i rnlinn Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Mathematical Modeling With Graphs l A mixed graph roadmap mode Gas iammre Tram s are yam gm w mm Fingw r w m mush own 51m am b Flgure117 Roadmap of landmark in a sundl mwu lnhoducuon to Graph Mod is e BlNF739 SolkaWeller BlNF739 11 Mathematical Modeling with Graphs l A digraph model ofa corporate hierarchy Dept Head Supervisors Stall Members l FigureI18 A rmpuralr ii l39lu 39lly inuoducuon to Graph Models BlNF739 SolkaWeller BlNF739 11 Degree of a Vertex Def Adjacent vertices are two vertices that have an endpoint in common Def Adjacent edges are two edges that have an endpoint in common Def If a vertex VlS an endpoint of edge 5 then V is said to be incident on e and e is incident on V Def The degree or valence of a vertex Vin a graph G denoted degV is the number of proper edges incident on v plus twice the number of self loops introduction to Graah Models BINF739 SolkaWeller BINF739 11 Degree of a Vertex Def The degree seguence of a graph is the sequence formed by arranging the vertex degrees in nonincreasing order Exzunhle 119 l igurr I in Nllli n l39uiili and H legim lilli w ll 1 l llllgt n3 w Figure 119 A graph zmil ilx t lvgl39ui SDqllvuL l39 introduction to Graah Models BINF739 SolkaWeller BINF739 11 Degree of a Vertex The degree sequence does not uniquely determine the graph Ex nlpli 111 i v l l H lwngt lvll11r39v nl 391 wi lp lii G i gt rwu graph Wm 1011quotbd llllt39lll l 5 are 1011 Figure 11110 Introduction to Graph Models BINF739 SolkaWeller BINF739 11 Degree of a Vertex 39 rl 1 1 ill 7 I39 l rmlt ml Ilw a mm In app wan numb kvl39wIlrluHINril m wwwmIlug Humps in a ip gr 39uylv 1111 l39n ruiixivud 1 urnpli Mme lu 7 139 vii awn w ilrquotl3911nli lli llh iwlrnnl l39ul lllr39 lnm wMA lilml 1mm iiunilv llw w no rm mm pun l39ni mm m u u 39l39hrn win My pm in n ugly wily H I Wm mum at urinal le wmmg mm i 41qu 1 Introduction to Graph Models BINF739 SolkaWeller BINF739 1 Degree of a Vertex Thm 112 Euler s DegreeSum Theorem The sum onhe degrees onhe vertices of a graph is twice the number of edges ihwmumuh m Graph Mudds EINF739 ErikaWale awrm Grap 39c Sequences Def A sequence ltd1 d2 dngt is said to be graphic if there is a permutation of it that is the degree sequence of some simple graph Such a simple graph is said to realize the sequence ihwmumuh m Graph Mudds EINF739 ErikaWale awrm 11 Indegree and Outdegree in a Digraph Def The indegree of a vertex v in a digraph is the number of arcs directed to v the outdegree of vertex v is the number of arcs directed from v Each self loop at v counts one toward the indegree of v and one toward the outdegree Introduction in Graph Models BIN F739 SolkaWeller BIN F739 I 12 Common Families of Graphs l 4 A 5 Figure 121 The rst ve rumpletn graphs Mo Figure 122 Two bipartito graphs Introduction in Graph Models BIN F739 SolkaWeller BIN F739 12 Common Families of Graphs A Figure 123 The smallest nouhiparrire simple graph Figure 124 The complete bipartite graph Ky l Introduction to Graph Models BINF739 SolkaWeller BINF739 12 Common Families of Graphs Def A regular graph is a graph whose vertices all have equal degree Tenahedrcn Dodecahedron icosahedrcn Figure 125 The w plalnuix graphs Introduction to Graph Models BINF739 SolkaWeller BINF739 I 12 Common Families of Graphs The Petersen graph a poster child for conjecture testing and theorem proving Introduction in Graph Models BIN F739 SolkaWeller BIN F739 12 Common Families of Graphs We can use graph theoretic models to model chemical compounds Working Group on ComputerGenerated Conjectures from Graph Theoretic and Chemical Databases I I L quot quot rIItners J quot 39 l rnI G7001 DataF abstractshtml 00 ngremJ A 2I39egular graph I Pprvsentlng tlJL uxygvn mnlut39ulr in Introduction in Graph Models BIN F739 SolkaWeller BIN F739 I 12 Common Families of Graphs 82 A El Figure 128 Bouquets H and 14 D 2 3 V V Figure129 Dipolus m and In Introduction to Graph Models BINF739 SolkaWeller BINF739 I 12 Common Families of Graphs mupmmph ml lm m 1 llml m in lmu hllll1l llill Hilll u 5 in on a iuulq ll39ngill lmv ni i m l lu A pull graph 139 lgt i t m l ii v ill nl39 ll v r 1 w quot x l 39 nll l u r l Exnmplr 127 I39nli manila 1quot Mill l 39xrv limi lli l l lllr l2 In P2 39 Pa o cAo Flgure1210 Path Ri39zlpLh Iquot and P Introduction to Graph Models BINF739 SolkaWeller BINF739 12 Common Families of Graphs DEHNI I UN 339le graph l5 1 gtilglr ri39lwx Ill 1 M39llllawl rr H simple enile 39 ll ll ll 5 lfm IlmI ran lu39 ulmmn w lllill xll ul39 il x rliwm alul ngr39s lie in lllglr39 l II VIV All IIJ39v l39lvx vywlr graph lrll1ll lt394l 39 Exmuplv 128 I39ln39 Wy ll gl39nplh i 1 mu 5 arr lumn in Figurv lr39lvl l o C Figure 1211 Cycle graphs 391 393 and Cl C4 Introduction to Graph Models BINF739 SolkaWeller BINF739 12 Common Families of Graphs r graph hear r l39lv xrwl i 1h mMxi 1 Ir Tili39 hypcntnhvgraph QH l5 Ilw llrrvqnln an A lg balmPu 1m verlilm ll and wl whim or Ivnmi u vml mi um mm only n my mun in mi mu m Introduction to Graph Models BINF739 SolkaWeller BINF739 12 Common Families of Graphs 4 3 2713 Tlu lill l39lllalll graphs viir153 l rrirrli 39 J39 and r39irv H I Introduction to Graph Models BINF739 SolkaWeller BINF739 lli 12 Common Families of Graphs t whle will 1 39Il rpm y r t f I 1 M inm Him IlliFilr llPl m L mm 3 s m ctiuu vnllui nl wrwlr uruixh is I an in s 1 1mm nmw mm grule if it a an impismnci will in in MI in Ilw graph in l39igurr l 3 4 ix an lmm ml mph for he fullAnn haggm rails l1 ll7 d C Figure 1214 Au interval graph Introduction to Graph Models BINF739 SolkaWeller BINF739 12 Common Families of Graphs Topics in intersection graph leory SIAM Monographs on Discrete Mathematics and Applications 2 Terry A McKee and ER McMorris Society for Industrial and Applied Mathematics SIAM Philadelphia PA 1999 vii205 pp ISBN 0898714303 QA 166105M34 Decomposition of overlapping protein complexes A graph theoretical method for analyzing static and dynamic protein associations Zotenk012 Katia S Guimaraesl3 Raja Jothil and Teresa M Przytycka Algorithms for Molecular Biology 2006 17 Introduction to Graph Models BINF739 SolkaWeller BINF739 12 Common Families of Graphs lg ui ii39 iiiil ll u my a l39 ili j llrl i rl39liX l39iii39 H irEi39iv rim Tlii inr graph Litii ul iii m ailiwiii i iii ili il39 iliv rivrimiiuiiiliiia 2 I Ail ll lliPN iiil rvilllllill l Lilli i ilii Hllrl39sr llltll giziiili iIJ39 iiJilllilHl in lh wiitliiuiiii Wu Exmnple 1243 Figiiw 391 I1 mini i qiiipli 1 Mil ii llllr graph Lllj o LG Figurei21e A graph and it 1 giapii Introduction to Graph Models BINF739 SolkaWeller BINF739 20 13 Graph Modeling Applications 0 A bipartite encoding a document collection Words Documents Introduction to Graph Models BINF739 SolkaWeller BINF739 13 Graph Modeling Applications A bipartite encoding of a gene expression experiment 1 genes samples Introduction to Graph Models BINF739 SolkaWeller BINF739 21 13 Graph Modeling Applications Evolution of coauthor networks httpwwwscimapsorgdevbigthumbphpmapid54 Inn39oduction in Graph Models BIN F739 SolkaWeller BIN F739 i 13 Graph Modeling Applications 0 Classroom friendship k dat Dark lines indicate reciprocated relationships Random Effects Models for Network Data 2003 Peter Hoff Proceedings of the National Academy of Sciences Symposium on Social Network Analysis for National Security Inn39oduction in Graph Models BIN F739 SolkaWeller BIN F739 22 13 Graph Modeling Applications meadow ieai wxiiow beene pussy Wiilnw nrunze ye game warmer sawiiy Hea beeiie ganer W snake Figure ila Thr food web in a Canadian willow fm39vst dmnon to G is BINF739 SoiKaWeiier BINF739 13 Graph Modeling Applications 911 Network inwodmnon to Graph Modeis BINF739 SoiKaWeiier BINF739 3 Graph Modeling Applications Graph Size 500 Mutual Information Threshold 1 Amhnu nodes are documents threshold determines which words are important edge between documents that share important words Edge between i and if M is large 1mm lMylerl Introduction to Graph Models BINF739 SolkaWeller BINF739 14 Walks and Distance Def In a graph G a walk from vertex V0 to vertex I is an alternating sequence a 51 V1 52 ml Vm err Vngt of vertices and edges such that endptse 14 V for 39 1 n If Gis a digraph or a mixed graph then Wis a directed walk if each edge e is directed from vertex V to vertex v ie taile V and headEl 14 Def The length of a walk or a directed walk is the number of edge steps in the walk sequence Def Closed walks begin and end on the same vertex while open walks begin and end on differentvertices Introduction to Graph Models BINF739 SolkaWeller BINF739 24 14 Walks and Distance Figure 141 lwgmpliir uljunvui39y of the uurthezm tvm stalls Introduction to Graph Models BINW39 SolkaWeller BINF739 14 Walks and Distance mm i ii Klumimzrr iivlts will Examplo 142 in tin Mzukm mm mm illm mili wwun uh 39 2 E 2 I i39ilfllrb In rm tun mn lmxm uul llu Ii SwiltllP lim39l lLl US lgt 1 I 39 f HlulilIrb tilting u mllt m an Murltm diagram I qua lt llh prmlnri 0 llll H39z illMth bail iln pmimivilui ilml iln lil wi r nil l39ollmvllml wall iliil39iug iuvxpmimenial ii39lnl Hm itquot ln39nlml39ilin mm n We rurs lln snarlmg l39rnm39rqunlsl quot my FigureIAZ Markov prm Pss from Application 1312 Introduction to Graph Models BINW39 SolkaWeller BINF739 25 14 Walks and Distance Def The distance dst from a vertex sto a vertex tin a graph Gis the length of a shortest st walk if one exists othenNise dst infinity For digraphs the directed distance dst is the length of the shortest directed walk from sto t Figure L45 Gvugraphii adjacency of tlxr nurlhraxlern states Inlroduction to Graph Models BINF739 SolkaWeller BINF739 I 14 Walks and Distance 512146 How might you nd a shortest walk from to i in this graph Inlroduction to Graph Models BINF739 SolkaWeller BINF739 26 14 Walks and Distance Def The eccentricity of a vertex v in a graph G denoted ecci is the distance from v to a vertex farthest from V That IS eccv maxxdG d v x The diameter of a graph G denoted diamG is the maximum of the vertex eccentricities in G or equivalently the maximum distance between two vertices in G That is diamG maxerG eccx maxx s dxy Introduction to Graph Models BINl739 SolkaWeller BINF739 14 Walks and Distance Def The radius of a graph G denoted ratG is the minimum of the vertex eccentricities That is rad G 2 miners eccx Def A central vertex v of a graph Gis a vertex with minimum eccentricity Thus ecci ratG i Ilir giziivli ul39 I iuiir l 17 lwlmii ll x ilmmuici l m39liirwil 1 m y i u ii iii win mi 4 lmv mumrm 2 mil all aim r r i39i39minlilh Tlm llll empli lm liiillllr 23Hl41V ll1lfl i l lll il39 Figure 147 A graph with Iipunctvi39 1 auil radius 2 Introduction to Graph Models BINl739 SolkaWeller BINF739 27 14 Walks and Distance Def Vertex Iis reachable from vertex uif there is a walkfrom uto l Def A graph is connected if for every pair of vertices uand l there is a walk from uto l Def A digraph is connected if its underlying graph is connected lnuoducuon to Graph Models BINF739 SolkaWeller BINF739 14 Walks and Distance Figure148 A uonr mmectrd graph with three components inuoducuon to Graph Models BlNF739 SolkaWeller BlNF739 r 14 Walks and Distances Def Two vertices u and v in a digraph D are said to be mutually reachable if D contains both a directed uiwalk and a directed Vg walk Def A digraph D is strongly connected if every two of its vertices are mutually reachable Inwocucumto ra hModes BINF739 SolKaWeller BINF739 14 Walks and Distances v V u x w Figuve149 A struneg i39UluH l39lf il digraph Inirocucuon to Graph Models BINF739 SolKaWeller BINF739 15 Paths Cycles and Trees Def A trai is a walk with no repeated edges Def A th is a trail with no repeated vertices except possibly the initial and final vertices E X d 2 li1ur uvli t r If I n C 3 gure 151 Wall ii i not a trail and Imil I is not a path Introduction to Graph Models BINF739 SolkaWeller BINF739 15 Paths Cycles and Trees Def A nontrivial closed path is called a gycle De An acyclic graph is a graph that has no cycles Def A cycle that includes every vertex of a graph is called a hamilton cycle Def A hamilton graph is a graph that has a hamilton cycle Introduction to Graph Models BINF739 SolkaWeller BINF739 30 15 Paths Cycles and Trees Li Z V v w x Figure 153 A humiltmuan grnph Inimduction to Graph Modeis BINF739 SoikaWeiier BINF739 15 Paths Cycles and Trees Def An eulerian trail in a graph is a trail that contains every edge of that graph Def An eulerian tour is a closed eulerian trail Def An eulerian graph is a graph that has an eulerian tour Inimduction to Graph Modeis BINF739 SoikaWeiier BINF739 15 Paths Cycles and Trees Figure 156 An uulvriau graph Inimductinn m Graph Madels Emir39 SaraWaller BINF739 15 Paths Cycles and Trees Def The girth of a graph G with at least one cycle is the length ofa shortst cycle in G The girth ifan acyclic graph is undefined Figure 157 A graph will girth 3 Inimductinn m Graph Madels Emir39 SaraWaller BINF739 15 Paths Cycles and Trees Def A m is a connected graph that has no cycles a Aulngeneralad HTML 7 Micrnsn Internal Exptm n at W Fame mt Help 3 e ack v E g 0 52m Favantes gm 1 maresc7err5ey231tpttnayemsnemieswsu3nzmi vl gt Ga Llrtl39 gt Intersects Imm strength lmerstrenwlh a My man Introduction to Graph Models BINF739 SolkaWeller BINF739 Tree 15 Paths Cycles and Trees run an Help Search Tree v V t JD protein cell express beta express induc activ bind peptid express enzym activ isol infect gene patient infect strain lt na gene sequenc protein can activ vtru diseas clinic water and membran adsorpt membran surfac phase adsorpt ion ion SOIL 90393quot separ membran surfac extract phase separ water phase so liquid ms capillari r adsorpt extract surfac 50quot water remov soil water pcb degrad wastewat sludg contamin remov degrad pcb pcdd polychlorin dioxin congen sediment Introduction to Graph Models BINF739 SolkaWeller BINF739 33 16 Vertex and Edge Attributes More Applications Def A weighted graph is a graph in which each edge is assigned a number called the edge weight Shortest Path R3 Geodesic and Manifold Geodesic ISOMAP Geodesic and Associated Nearest Neighbor Graph Introduction to Graph Models BINF739 SolkaWeller BINF739 16 Vertex and Edge Attributes More Applications Definition Minimal Spanning Tree MST The collection of edges that join all of the points in a set together with the minimum possible sum of edge values The edge values that will be used here is the distance measures stored in our interpoint distance matrix 2 W a j i m g XVTKBOLI A graph Associated MST Introduction to Graph Models BINF739 SolkaWeller BINF739 34 BINF 739 SPRING 2007 SOLKAWELLER Chapter 5 Connectivity BINF739 SolkaWeller Spring 2007 Introduction Some graphs are more connected than others Some graphs can be disconnected by removal of a single edge Some remain connected even after the removal of numerous edges Useful measures vertex connectivity edge connectivity BINF739 SolkaWeller Spring 2007 I Applications of Connectivity Network vulnerability analysis Re a s Telecommunication networks Organizationalnetwor ter n twor Biological networks EINF739 ErikaWalla Swing 2mm 51 Vertex and Edge Connectivity iluwxmom Li I 1 mm a div L oi i n u m l M r h my mama N l inn ml Dr 5 it M u dumnmn n r m 41 m Human mm mm in w a WWW mmin n n smilr rrm m rum u ml 7 u lm mavrompuuenh unlu dgn by um um u m 440 ml mummug m min ass i v n ml mil irn m m n lynlwwlxe in mm n n39rlttxcmmul m or my A WM graph vilyulu mumml graph 4 m mi mmy u ii m min mum 1 mm H w u nu i ml lmw ompmvul uouqdlMdil Nune lei um i mumm mum v i EINF739 ErikaWalla Swing 2mm I 51 Vertex and Edge Connectivity unnxllm gmph u I k ummzluhl n m rmquwa and mm 2 I IN nus mmuwm mm um h mm m y mm I Im m In A mum nnmiw u x x mmw39r mm m 4 nulnl x Mum 1 ml mum nu mum w dethl u nnmumm mlmlwr of Ilgn apL an Jgtummw hm Hm 1 u x y mmmm u D nu m quotr n ndgm n m l m mam41gp 1umwmm and M Wm M nquot 1 m A an n mm 1 ammg Sa kaWeHev 5Wan 2mm I 51 Vertex and Edge Connectivity Exmxph 5 n he mph Iwm m mm s z 1 139 Wm w m wquot u lhne dl errm 2am vmmm Ind u 5 m Io per lhu hue s no quotmunex lhus A u v gt41 5 M 1 he unique brltmem bag cm sly19h a mu quotMy m m hm u Mg m map 39 b v G y w ngmsm A graph 1 with mm 2 and mm Appnmnmi an mum Hunualnhl m wmmm u mm K m m w m mum nmdelmlumA WWW mm u m Mum nunWurk w 72mm mummm muqu m mm Anyr w 115 an w mew BINF739 Sa kaWeHev 5Wan 2mm 51 Vertex and Edge Connectivity m lurk Sim w nu urlt xrmmuniwliy W my I 9 WM wryPi mnummmlm u nfv View 4 mun u u n mm mm lllrmlxhoiu mu cimpm an latMew mum umwu unwind mm b n asunderLian Pm umiiou 51 I r in 44 or am u an minimum 4m Am Hi1quot m m minimum m h N uh m P of m y I 3 mm n1 mm M mum 5mm riiguumr m k 4 mm m mmd39ni m mm sepanues m the myquot mum on o mnw mom 4 5 A ignitionuni our rildpmm u rlrh rm u mi Mg m nth 07 mm vs I u vlrx Mlmnmnnw v mid v w Winning unwrile MW 1114 m ofrlwmmuiiminmn mu mmwmiu m quotmark lion prayemh uuhhhsl m impl l m m 5 p n f mu Emma SaiksWdiev Spying 2mm 51 Vertex and Edge Connectivity Pnlpnnilinu 512 I m mnlmm 1 in I quotUm mumnnmmi r m mi i I W 39nrnlmn i I nmfz in WWW I I m hm A mm xlmmpt u ilgrm u uuerJn u mm mm 4 uf 1m quotItquot i m a mu m my mum n m ml MN MW m i wig n WWW 5 z u M WWW m rum 0 m i it k is o Emma SaiksWdiev Spying 2mm 51 Vertex and Edge Connectivity Relationship Between Vertex and Edge ConnectIVIty a Lm 1k am dqeulnkawmmlm 11mph r urkgd mm on may i r 4 y n litmumw 1mm min n r t l 41lugmplil n I n 7 WWW rqmum 515 It i 1 im x nwmrlwl mph Hm Mm 3 K in nunum n v111 munmmmny Humming awm ErikaWale sum 2m7 51 Vertex and Edge Connectivity 395 int Paths and Vertex Whitney s Theorem Imlml um Vin mm m l quot4 x l innrunquot digjuiul v w quotJ39uxmvcnl am i 10le in u ly i mm mm quotm mm quotn iflmrmh m m 0mm dummy W1 Wm n1quot Two ways to travel between u and v 9 fault tolerance awm ErikaWale sum 2m7 51 Vertex and Edge Connectivity Internally Disjoint Paths and Veltex Connectivity Whitney s Theorem Corollary 518 Let G be a graph with at least three vertices Then G is 2connected iff any two vertices of G lie on a common cycle BINF739 SolkaWeller Spring 2007 51 Vertex and Edge Connectivity Internally Disjoint Paths and Veltex Connectivity Whitney s Theorem M will my ll m wrnrm Tin n llir nllmmlg w l jrr uner39l 4 In W m r m in r wrur 39uul um llww l ii pail runlmmng all Ilnv ll Fmrnn IImvr thlmrl wru ol 2 mm is mm Minimum all mm 7 m m mm Mum Willa um mm h W rmlammg w m 1 3 Mlill l ill nirl mmmn ljlr ilnpl 39 BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Whitney s Synthesis of 2Connected il Graphs and 2Edge Connected Graphs Def A path addition to a graph G is the addition to G of a path between two existing vertices of G such that the edges and internal vertices of the path are not in G A cycle addition is the addition to G of a cycle that has exactly one vertex in common with G BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Whitney s Synthesis of 2Connected Graphs and 2Edge Connected Graphs Def A Whitne Robbins s nthesis of a graph G from a grap H is the sequence of graphs G0 G1 G where G0 H G G and Gi is the result of a path or cycle addition to GM for i 1 If each Gi is the result of a path addition only then the sequence is called a Whitney synthesis Q g Figure 521 A Vhiruvy Synllu39aiH 0mm cum graph A BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Whitney s Synthesis of 2Connected Graphs and 2Edge Connected Graphs Lemma 521 Let H be a 2connected graph Then the graph G that results from a path addition to H is 2connected Thm 522 Whitney Synthesis Theorem A graph G is 2connected iff G is a cycle or a Whitney synthesis from a cycle BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Whitney s Synthesis of 2Connected Graphs and 2Edge Connected Graphs Lemma 523 Let H be a 2edgeconnected ie bridgeless graph Then the graph that results from a path or cycle addition to H is 2connected Thm 524 WhitneyRobbins Synthesis Theorem A graph G is 2edge connected iff G is a cycle or a WhitneyRobbins synthesis from a cycle BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Tutte s Synthesis of 3 Connected Graphs Review from Section 24 The nspoke wheel or nwheel Wm is the join K1 CH of a single vertex and an ncycle The ncycle forms the rim of the wheel and the additional vertex is is hub 1 xx x Y Figure 524 Thv spukt whwl 1i 1 BIN739 SOlkaWellei Spring 2007 52 Constructing Reliable Networks Tutte s Synthesis of 3Connected Graphs Thm 525 Tutte Synthesis Theorem A graph is 3connected iff it is a wheel or can be obtained from a wheel by a sequence of operations of the following two types 1 Adding an edge between two nonadjacent vertices 2 Replacing a vertex vwith degree at least 4 by two new vertices V1 and 12 joined by a new edge each vertex that was adjacent to Vin G is joined by an edge to exactly one of V1 and 12 so that deg V1 gt 3 and deg 12 gt 3 BINZ739 SolkaWeller Spring 2007 52 Constructing Reliable Networks l39utte s Synthesis of 3 Connected Graphs E 7 39 gt V Figure 525 A lsnp 39mm synthesis of flu i39uln graph 1 1 All but the second step are operations of type 2 BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks l39utte s Synthesis of 3 Connected i Graphs Application 521 Construction of a class of reliable networks Given positive integers n and k with k lt n nd a k nected nvertegtlt graph having he smallest possible number of edges Def hkn denotes the minimum number of edges that a k connected graph on n vertices must have h1n n1 since a spanning tree is a connected subgraph with the least number of edges Def For any real number X the floor of X denoted oorgtlt is the greatest integer less than or equal to X and ceiling of X denoted ceilgtlt is the smallest integer greater than or equal to X BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Tutte s Synthesis of 3 Connected Graphs Prop 526 Let G be a kconnected graph on n vertices Then the number of edges in G is at least ceilkn2 That is hkn gt ceilkn2 BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Harary s Construction of an Optimal k Connected Graph Frank Harary gave a procedure for constructing a k connected graph Hk n on n vertices that has exactly ceilkn2 edges for k gt 2 The construction of the Harrary graph Hkln begins with a n cycle graph whose vertices are consecutively numbered 0 1 2 n 1 clockwise around its perimeter 0 mm riny 2 5 Figure 526 Harary iminuctim shu39rr will an ill39yl lf graph BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Harary s Construction of an Optimal k Connected Graph Def Let i andj be any two integers from the set 0 1 n1 The mod n distance between i and j denoted j iln is the smaller of the two values ji and n ji 48 Figure 527 Hm39m39y graphs Ill ml 1 Case 1 k even HZrn has exactly rn edges LTR Let k 2r Vertices i and j Hence H2rn has thedeSired are joined by an edge if U number of edges smce rn knZ ceilkn2 in lt r BINF739 SolkaWeller Spring 2007 52 Constructing Reliable Networks Harary s Construction of an Optimal k Connected Graph 0 Case 2 kodd and n ever H58 7 7 1 Let k 2r 1 Start witl Hzn n and add the n2 j 2 diameters of the original K 1 cycle That is an edge is g 39 3 4 drawn between vertices i and nZI for 0 m Figure 528 Harmy graph 12 i n2 1 thus the total number of edges in Hzmln equals m n2 2r1 n2 kn2 ceilkn2 11 11h four tlinnntm s BINF739 SolkaWeller Spring 2007 12 52 Constructing Reliable Networks Harary s Construction of an Optimal k Connected Graph Case 3 k and n both odd H 0 Let k 2r 1 Start with graph 59 a 1 H2 n and add n12 quasi 7 2 diameters as follows First 6 3 draw and edge from vertex 0 to vertex n12 and from vertex 0 to vertex n12 Then draw an edge from vertex i to vertex i n12 fori 1 n 32 The total number of edges in Hzmln equals rn n12 2r1n12 ceilkn2 since kn is odd BINF739 SolkaWeller Spring 2007 Figure 529 Harm39y graph 7 in n pllh w luzhitlizm muns 52 Constructing Reliable Networks Harary s Construction of an Optimal k Connected Graph Thm The Harary graph Hkn is kconnected Corollary 528 The Harary graph Hkn is a k edgeconnected nvertex graph with the fewest possible edges BINF739 SolkaWeller Spring 2007 13 52 Constructing Reliable Networks Harary s Construction of an Optimal k Connected Graph Algorithm 521 Cunsh39ul39 ng m1 Optimal IrConur39ctenl nVex tcx Gilt mng l mini H mm I lt IllIill pmm H ulm39d lLlawil lululine 4le ll mil ilu gtlvll All II in in u mluml 39l lllgt will lalzrrl n n n l n 7 39J ylimwl Helium ilTiifl 1mm in ler lwl39 lVIll39rquotl ml j lj lm lamrm ln mmiim mu u 11 11 v 1 Wm mm graph 1 I39lw ll u i M u for i n In L 7i l39mw r we lwlle i39lx mm mm mm 1 7 l39lsr 1 m m HJQ rum m H Iv vi39le l n lmru39mu wrm inwl wriv fr if i BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Primaldual optimization pairs are optimization pairs wherein one problem involves the maximization of some objective function while the other problem involves the minimization of an objective function A feasible solution of one of these problems provides a bound for the optimal values of the other problem weak duality If the optimal value of one problem is equal to the optimal value of the other problem then this is called a strong duality BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Def Let uand Vbe distinct vertices in a connected graph G A vertex subset or edge subset Sis uv separating or separates uand v if the vertices u and vlie in different component of the deletion subgraph G 5 Thus a u Vseparating vertex set is a vertexcut and a UV separating edge set is an edgecut BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Exmnplt 511 lur llw llquotll l m l n w quot Hl rirxrvm l u l 1 iv m in I 1 y l l w mil llml 39 llillllllllVAIW w w I l y iinulimuilvrsw 39 39ui viirll39l Milli Figure 531 Vritux and edge cuts that zm mu Sk39piu39atiug wx BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems A PrimalDual Pair of Optimization Problems Maximization Problem Determine the maximum number of internally disjoint u v paths in the graph G Minimization Problem Determine the minimum number of vertices of graph Gneeded to separate the vertices uand v BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems A PrimalDual Pair of Optimization Problems Prop 531 Weak Duality Let uand vbe any two nonadjacent vertices of a connected graph G Let PW be a collection of internally disjoint u v paths in G and let 5W be a u vseperatling set of vertices in G then PW lt 5W Cor 532 Let uand vbe any two nonadjacent vertices of a connected graph G Then the maximum number of internally disjoint u Vpaths in Gis less than or equal to the minimum size of a u v separating set of vertices in G BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems A PrimalDual Pair of Optimization Problems Corollary 533 Certificate of Optimality Let uand V be any two nonadjacent vertices of a connected graph G Suppose that PW is a collection of internally disjoint uVpaths in G and that 5 is a UV separating set of vertices in G such that PV 5V Then PM is a maximumsize collection of internally disjoint UV paths and SUV is a minimum size uVseparating set BINF739 SokaWeller spring 2007 53 MaxMin Duality and Menger s Theorems A PrimalDual Pair of l Optimization Problems ll win mm ph l39uuwlwr up ulvll41mn minl 3 3 in I w r y m u l vl rum39vwm n mllnliun P ml Ilnvs nmrn xll llllvllll In l v ml up w s in 4 h u w a mrwuwx kip l mini ix 39 l n mummuhw mumwn mum mm mm w mun mm r l 5 Figure 532 BINF739 SokaWeller spring 2007 53 MaxMin Duality ancl Menger s Theorems Menger s Theorem Thm 534 Menger s Thm Let uand ibe distinct nonadjacent vertices in a connected graph G Then the maximum number of internally disjoint uipaths in Gequals the minimum number of vertices needed to separate uand v BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Variations and Consequences of Menger s Theorem Def Let sand tbe nonadjacent vertices of a connected graph G Then the local vertex connectivity between sand 139 denoted Kvsy is the size of the smallest stseparating vertex set in 6 Lemma 535 Let Gbe a connected graph containing at least one pair of nonadjacent vertices Then the vertexconnectivity 196 is the minimum of the local vertexconnectivity 191517 taken over all pairs of nonadjacent vertices sand 139 BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Variations and Consequences of Menger s Theorem Thm 536 Whitney s k Connected Characterization A nontrivial graph G is k connected iff for each pair u iof vertices there are at least kinternally disjoint UV paths in G Cor 537 Let G be a k dimensional graph and let U V1 V2 Vk be any kJ distinct vertices of G Then there are paths Pfrom uto vi fori 1 k such that the collection R is internally disjoint BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Variations and Consequences of Menger s Theorem Thm 538 Dirac Cycle Thm Let Gbe a k connected graph with at least kJ vertices for k gt 3and let Ube any set of kvertices in G Then there is a cycle in Gcontaining all the vertices in U BINF739 SolkaWeller Spring 2007 53 MaxMin Duality ancl Menger s Theorems Analogs of Menger s Theorem Prop 539 Edge Form of Certi cate of Optimality Let uand vbe any two vertices of a connected graph 6 Suppose PWis a collection of edgedisjoint u v paths in G and 5Wis a u vseparating set of edges in G such that PW 5W Then PW is the largest possible collection of edgedisjoint u v paths and SW is the smallest possible u vseparating set In other words each is an optimal solution to its respective problem BINF739 SolkaWeller Spring 2007 53 MaxMin Duality and Menger s Theorems Analogs of Menger s Theorem Thm 5310 Edge Form of Menger s Thm Let uand vbe any two distinct vertices in a graph Then the minimum number of edges of Gneeded to separate u and v equals the maximum size of a set of edge disjoint u Vpaths in G Thm 5311 Whitney s kEdgeConnected Characterization A nontrivial graph Gis k edge connected iff for every two distinct vertices u and V of G BINF739 SolkaWeller Spring 2007 20 53 MaxMin Duality and Menger s Theorems Analogs of Menger s Theorem 39pln 533 lnr lllr ur39nrxlr linml llr liiurv waxy in Hull leI39 vzlulr 1w purl MM u my wrurmlmuv nl l llm rlu mrnmmm minim r lhlnllll m Mllh dhi lllr mnmmnmuv ll r w w mmnm Al w lmvlr 7 Figure 535 LTR BINF739 SolkaWeller Spring 2007 I 54 Block Decompositions Def A block of a loopless graph is a maximal connected subgraph Hsuch that no vertex of His a cutvertex of H Thus if a block has at least three vertices then it is a maximal 2connected subgraph The only other types of blocks in a loopless graph are isolated vertices or dipoles 2 vertex graphs wit a single edge or multiedge Remark The blocks of a graph G are the blocks of the components of G and can therefore be identi ied one component G at a time Also selfloops or their absence have no effect on the connectivity of a graph For these reasons we assume throughout this section except for the final subsection that all graphs under consideration are loopless and connected BINF739 SolkaWeller Spring 2007 21 I 54 Block Decompositions mi in 1mm i i im mu mum ini M iii ulygmiyih 4m ii in ii 1 i imi in U y w x l S v 2 Figure 541 A graph with four Much Remark By def a block Hof a graph Ghas no cutvertices of H but H may contain vertices that are cut vertices of G For instance in the above figure the vertices W X and yare cut vertices of G BINF739 SolkaWeller Spring 2007 I 54 Block Decompositions The complete graphs Kn have no cut vertices Prop 541 Every non trivial connected graph G contains two or more vertices that are not cut vertices Prop 542 Two different blocks of a graph can have at most one vertex in common BINF739 SolkaWeller Spring 2007 22 I 54 Block Decompositions Corollary 543 The edgesets of the blocks of a graph G partition E9 Corollary 544 Let Xbe a vertex in a graph G Then XiS a cutvertex of Giff XiS in two different blocks of G Corollary 545 Let B and 52 be distinct blocks of a connected graph of G Let y and y2 be vertices in B and 52 respectively such that neither is a cutvertex of G The vertex y is not adjacent to vertex yz BINF739 SolkaWeller Spring 2007 I 54 Block Decompositions Def The block graph of a graph G denoted BLG is the graph whose vertices correspond to the blocks of G such that two vertices of BLG are joined by a single edge whenever the corresponding blocks have a vertex in common Exzunplv 342 I39m 3 l3 m l guile x ml in rim1 ginpll is lle E 3 B B 5 o A s o B 4 Bi 32 3934 Ba G BLG Figure 543 A graph and its lulmk graph BINF739 SolkaWeller Spring 2007 23 54 Block Decompositions Def A leaf block of a graph Gis a block that contains exactly one cutvertex of G Prop 546 Let Gbe a connected graph with at least one cutvertex Then G has at least two leaf blocks BINF739 SolkaWeller Spring 2007 54 Block Decompositions Finding the Blocks in a Graph Algorithm 541 BluIkFiuding v u39iimwiml graph 1 Ni i w illquot r r I39llLy R u ill llwl ml 3 wly A at hm l 4 l I mil lln vl K 1 i um mm 11 grcqill r ivmmlwr lln39 In mum 1 U a m m llll minim mil 1 xlannlIrrl T 39 varn IV 171131 ft BINF739 SolkaWeller Spring 2007 24 54 Block Decompositions Finding the Blocks in a Graph Mp1 543 Tlir blow iir rrnip iii0iui riip grillli Hlimm ii rim 3 H mm Eu r iiiiu 1h ilnw ri rrliirli iir Hump Figure 544 A graph r um it ve Murksr BINF739 SolkaWeller Spring 2007 NETWORK BIOLOGY UNDERSTANDING THE CELL S FUNCTIONAL ORGANIZATION AbertL szo Barab s amp Zota39n V OtIal39 NATURE REVIEWS GENETICS Vol 5 2004 BINF739 SokaWeller Spring 2007 Degree Distribution Degree distribution The degree distribution P k gives the probability um a selected nod has exactly klinlxs P k is obtained by munting L c number of nodes Nk with k l 2 limb middividiug by e mnl l 139 39 in e I Irwl A A39 h ih F 39 39 39 39 system has a characta39 tic degree audllml there are no highly unheard nodes which are also known as hubs Bycomnm u powerlawd ee distribution indicmes that a few lulbs hold Iogdhermuncrolls small noch BOX 23 BINF739 SokaWeller Spring 2007 Scale free networks and the degree expouem ScaleFree Networks and the Degree Exponent on a BINF739 SokaWeller Spring 2007 Shortest Path and Mean Path Length Shortest path and mean path length LII II I II I I I I I u I I a L I A I I v r I I I I I I I I t I win the II I r I I I I I I I r I I I I I I n A m 3m mm node A to node B is often different from the distance M from B to A For example in part b of the gure BA l I I I I I h eas m I I A l I A I I I I I I m cm Aquot II A 39 39 A m t 39r39 I 39 39 VI lt I a an gmml I I II t I I x I II gt I I I a b Dirwed network BINl739 SolkaWeller Spring 2007 Clustering Coefficient Clustering coef cient In many networks if node A is connected to B and B is connected to C then it is highly probable that A also has a direct L I L I a link to C TL 39 L l U 39 u 33 CI anlkk I where quotI is the number of quot1quotquot 39 U 39 A 390 nodeI 39 quot In other words C gives the number of t39riangles see BOX 3 that go through nodelwheramp1s kk 1I39 39 39 39 number ul 39 r39 r 39 1 node I 39 394 node I 39 39 39 39 quot 39 one pair of node A s ve neighbours in part a of the C or I figure are linked together B and C which gives quotA l and CA 2 20 By contrast none of node F39s neighbours linkto each other giving CF 0 39 a 4 39 ltC 39 39 1 I IcIII Icncv of U I All impnrhnt nu Irreuf 39 39 39 I 39 Id which J 139 1 I a clusteringcoe icimt of all nodes with klinks For many real networks C k kquot which is an indication of a network s hierarchical diaracter 7 53 see BOX 2 The average degree lt kgt average path length lt f gt and average clustering coef cient lt C gt depend on the number of nodes and links N and L in the network By contrast the P k and C k functions are independent of the network s size I I I r I I u and they 39 K v lu be used to classify various networks BINl739 SolkaWeller Spring 2007 27 a NH ompmphme d o 11 113 I k r 0 39 D r AID S r E U E a 39 I i m4 E i w I mr39 EA ri quot we oz Gr 32 39w quot Expairnanlat llux v m ai GLC uphka rats H39de 39 rhnnn Inh Frommdt r 39 39 THsprs ProteinProtein Interaction Networks 4 w 1 g 41 V 39 th 390 av g an k t A v r nguve 2r Venn pmleln Imemcnan nelwmk A map at warmmrn rmeyacnm rn sacchamntvoec ceremae VINE S based m SHIN Y rlD39and quotEasuvanemrquot mummies that a Yew NDHN Armenia nodes mm are also KIWIH as hubs MOM Ihe newWk Dg hy The ragest ctusten wmch wntalns 43 m 5H prom 5 shown The com or a node mer me phenolsma sum or remwng me correspondm Wotan red rarer green nunr ethah omngs srow gymIn yeuw unxnmm Repmdmai Min permrwun mm m m o Maomman Magazmes ua BINF739 SolkaWeller Spring 2007 28 Random Networks anlmll nelwurkk Tl r 4 l nrm mnM V39l39lmmil exlremeh391 r mumpmmm Mquot N smaUwurld property Ac BINH39 SolkaWeller Spring 2007 I Scalefree Network BINH39 SolkaWeller Spring 2007 29 Hierarchical Network nodes of my replimred clusters connected In lllecolnml nod 01 llmald clummlllul mm A large lornode moduluhm replims ol mi orllod2 module m mm generated and he lo lilo uli mum he om module ullkll pmdutu J m mammal quotmu 2 l m goflllnlllsleling coe idml which follows cm kquotas1miglulinoolslopa I m um 1m man 7 on a Iogrlug plot lxee ligmt39 ct k pl Co A hierardliul mummy ilupliesllml Emlsnly rounpdml node an m of highly luslered mm with imuoll lmhveen live highly luuemd being mainlained by a few hubs Examples of Scale Free Networks As for direct physical interactions several recent publications indicate that protein protein interactions in diverse eukaryotic species also have the features of a scalefree network This is apparent in the protein interaction map of the yeast Saccharomyces cerew39siae as predicted by systematic twohybrid screens Whereas most proteins participate in only a few interactions a few participate in dozens a typical feature of scalefree networks Further examples of scalefree organization include genetic regulatory networks in which the nodes are individual genes and the links are derived from the expression correlations that are based on microarray data or protein domain networks that are constructed on the basis of protein domain interactions 3O Deviations from Scale Free Networks However not all networks within the cell are scale free For example the transcription regulatory networks of 5 cereV siae and Escherichia coli offer an interesting example of mixed scale free and exponential characteristics Indeed the distribution that captures how many different genes a transcription factor interacts with follows a power law which is a signature of a scale free network This indicates that most transcription factors regulate only a few genes but a few general transcription factors interact with many genes However the incoming degree distribution which tells us how many different transcription factors interact with a given gene is best approximated by an exponential which indicates that most genes are regulated by one to three transcription factors BINF739 SolkaWeller Spring 2007 One Take Away Message So the key message is the recognition that cellular networks have a disproportionate number of highly connected nodes Although the mathematical de nition of a scalefree network requires us to establish that the degree distribution follows a power law which is difficult in networks with too few nodes the presence of hubs seems to be a general feature of all cellular networks from regulatory webs to the moduleThese hubs fundamentally determine the network s behavior BINF739 SolkaWeller Spring 2007 Small World Effects and Associativer A common feature of all complex networks is that any two nodes can be connected with a path of a few links only This smallworld effect which was originally observed in a social study has been subsequently shown in several systems from neural networks to the World Wide Web Althou h the smallworld effect is a property of random networks scalefree networ s are ultra small their pat length is much shorter than predicted by the smallworld effect Within the cell this ultra small world effect was first documented for metabolism where paths of only three to four reactions can link most pairs of metabolites This short path length indicates that local perturbations in metabolite concentrations could reach the whole network very quickly Interestingly the evolutionarily reduced metabolic network of a parasitic bacterium has the same mean path length as the highly developed network of a large multicellular organismwhich indicates that there are evolutiona mechanisms that have maintained the average path length during evolution BINF739 SolkaWeller Spring 2007 Disassortative Nature of Cellular Networks FIGURE 2 illustrates the disassortative nature of cellular networks It indicates for example that in protein interaction networks highly connected nodes hubs avoid linking directly to each other and instead connect to proteins with only a few interactions In contrast to the assortative nature of social networks in which well connected people tend to know each other disassortativity seems to be a property of all biological metabolic protein interaction and technological World Wide Web Internet networks Although the small and ultrasmallworld prope x networks IS mathematically wellunderstoodf the orlgln 0f dlsassprtatlwty 168quot at networks remalns unexplalned thatslewlllqlllymnna ajnodsswhichaleslsoknmmashubslluldlhsllemmmlogetha m am Well lam Emll Tlecmolmelmm lg lnlns 43 mall Pro rm ullenolyplc sweet ol remmlng the comlmnulm protein llea lethal glean nonrlelhall omngs le awn yellow unxllawrl Remainva ps nlssloll quotom REF no Macmillan Magazines ua BINF739 SolkaWeller Spring 2007 Evolutionary Origin of Scale Free Networks The ubiquity of scalefree networks and hubs in technological biological and social systems requires an explanation It has emerged that two fundamental processes have a key role in the development of real networ First most networks are the result of a growth process during which new nodes join the system over an extended time period This is the case for the World Wide Web which has grown from 1 to more than 3billion web pages over a 10year perio Second nodes prefer to connect to nodes that already have many links a process that is known as preferential attachment For example on t e World Wide Web we are more familiar with the highly connected web erefore are more likely o ink to them row preferential attachment are jointly responsible for the emergence of the scalefree property in complex networ s Indeed if a node has man links neW nodes Will tend to connect to it With a higher probability his node Wlll therefore gain new links at a higher rate than its less connected peers and Will turn into a hub BINF739 SolkaWeller Spring 2007 Gene Duplication as a Path to Scale Free Behavior Growth and preferential attachment have a common origin in protein networks that is probably rooted in gene duplication Duplicated genes produce identical proteins that interact with the same protein partners Therefore each protein that is in contact With a duplicated protein gains an extra link Highl connected proteins have a natural advanta e it is not thatt ey are more or less likely to be duplicate but they are more likely to have a link to a duplicated protein than their weakly connected cousins and therefore they are more likely to gain new links if a randomly selected protein is duplicated This bias represents a subtle version of preferential attachment The most important feature of this explanation is that it traces the origin of the scale free topology back to a well known biological mechanism gene duplication BINF739 SolkaWeller Spring 2007 Gene Duplication as a Path to Scale Free Behavior Although the role of gene duplication has been shown only for protein interaction networks it probably explains with appropriate adjustments the emergence of the scalefree features in the regulatory and metabolic networks as well It should be noted that although the models show beyond doubt that gene duplication can lead to a scalefree topology there is no direct proof that this mechanism is the only one or the one that generates the observed power laws in cellular networks BINF739 SolkaWeller Spring 2007 Gene Duplication as a Path to Scale Free Behavior Two further results offer direct evidence that network growth is responsible for the observed topological features The scale free model predicts that the nodes that appeared early in the history of the network are the most connected ones Indeed an inspection of the metabolic hubs indicates that the remnants of the RNA world such as coenzyme ANAD and GTP are among the most connected substrates of the metabolic network as are elements of some of the most ancient metabolic pathways such as glycolysis and the tricarboxylic acid cycle In the context of the protein interaction networks cross me comparisons have found that on average the evolutionarily older proteins have more links to other proteins than their younger counterparts This offers direct empirical evidence for preferential attachment BINF739 SolkaWeller Spring 2007 The ogan ot dne scaietree topology tn conplex networks can be reduc to two basc rnecnantsrns gowdn and prefermual a attac nnmt Growth means that the network emerges dnrou n the subsequent t addmon of new nodes sudn as the new red no e that is added to the network dnat ts snown tn part a Preferential attadnment WEN that new node prefe to link to more connected nodes For egtlta le dne prooaotitty tnat dne red node Will oonnect to node 1 ts twtce as large as oonnecun to node 2 as dne degree ot node 1 crowdn and preteenuai attac rrent geneate hubs dnrougn a rtcn r 39 more connected a node ts the more llkdy ttts that new nodes wtii itnk to tt wntcn allows dne ntgnwc onnected n des to aogut re new links taster dnan dnetr less oonnected pees ln protetn tnteracuon networks scalefree mpologv seems to have l5 5 ortgn tn gene dupitcauon Part b snows a small protetn tnteacuon network blue and dne genes dnat enoode dne protetns grew Wnen ceis dlvl e oocas onallv one Me or several enes ae oopted twtce tnto dne ottsprtng s genone illustrate v dne grew and red circles Tnts tnduces growdn tn dne 31m Whamquot protetn tnteracuon network because now we nave an eltlra gme that enoodes a new proten red circle The new proten nas dne sane structure 5 the old one so they Olin interact with the same proteins Ulnmatdy tne rotens dnat tnteaced wtdn dne ortgnat dupitcated protetn wtll ac gatn a new tnteacuon to new promn protetns wtdn a large nunber ot tneracu ons tmd to gan link more oftm as ttts rrtore likeydnatdney teactwtdn dne rotetn dnat nae Th s a rrtecnantsrn dnatgeneat s preteenuat a indeed tn dne eltarrple dnat ts snown tn part b tt does not rrtater wntcn gene ts duplicated dne mostoonnected cmual protetn hub mmwmm gatns one trteracu on in contrast dne squae wntcn nas only one tnk gatns a new itnk only tt dne hub ts dupitcated WM L 4 3 at g o E Figure 3 The origin of the scalefree topology and hubs in biological networks Motifs Modules and Hierarchical Networks Cellular functions are likely to be carried out in a I highly modular manner In general modularity refers to a group of physically or functionally linked molecules nodes that work together to achieve a relatively distinct function Modules are seen in many systems for example circles of friends in social networks or websites that are devoted to similar topics on the World Wide Web Similarly in many complex engineered systems from a modern aircraft to a computer chip a highly modular structure is a fundamental design attribute Motifs Modules and Hierarchical Networks Biology is full of examples of modularity Relatively invariant protein protein and protein RNA complexes physical modules are at the core of many basic biological functions from nucleic acid synthesis to protein degradation Similarly temporally coregulated groups of molecules are known to govern various stages of the cell cycle or to convey extracellular signals in bacterial chemotaxis or the yeast pheromone response pathway In fact most molecules in a cell are either part of an intracellular complex with modular activity such as the ribosome or they participate in an extended functional module as a temporally regulated element of a relatively distinct process for example signal ampli cation in a signalling pathway BINF739 SolkaWeller Spring 2007 High Clustering in Cellular Networks In a network representation a module or cluster appears as a highly interconnected group of nodes Each module can be reduced to a set of triangles a high density of triangles is reflected by the clustering coefficient the signature of a network s potential modularity In the absence of modularity the clustering coefficient of the real and the randomized network are comparable BINF739 SolkaWeller Spring 2007 High Clustering in Cellular Networks The average clustering coefficient ltCgt of most real networks is significantly larger than that of a random network of equivalent size and degree distribution The metabolic network offers striking evidence for this ltCgt is independent of the network size in contrast to a module free scale free network for which ltCgt decreases The cellular networks that have been studied so far including protein interaction and protein domain networks have a high ltCgt which indicates that high clustering is a generic feature of biological networks BINF739 SolkaWeller Spring 2007 Motifs are Elementary Units of Cellular Networks The high clustering indicates that networks are locally sprinkled with various subgraphs of highly interlinked groups of nodes which is a condition for the emergence o isolated functiona modul Subgra hs capture s eci c patterns of interconnections that characterize a given networ at the local evel However not all subgraphs are equally signi cant in real networks as indicated by a series of recent observations To understand this consider the highly regular square lattice an inspection of its subgraphs would Ind very many squares and no triangles It coul correctly be concluded that the prevalence of squares and the absence of triangles tell us something fundamental about the architecture of a square latt39ce In a complex network with an apparently random wiring diagram it is dif cult to nd such obvious signatures of order all subgraphs from triangles to squares or pentagons are pro ably presen However some subgraphs which are known as motifs are overrepresented when compared to a randomized version of the same network BINF739 SolkaWeller Spring 2007 Motifs are Elementary Units of Cellular Networks For example triangle motifs which are referred to as feed fonNard loops in directed networks emerge in both transcription regulatory and neural networks whereas four node feedback loops represent characteristic motifs in electric circuits but not in biological systems Each real network is characterized by its own set of distinct motifs the identi cation of which provides information about the typical local interconnection patterns in the network The high degree of evolutionary conservation of motif constituents within the yeast protein interaction network and the convergent evolution that is seen in the transcription regulatory network of diverse species towards the same motif types further indicate that motifs are indeed of direct biological relevance BINF739 SolkaWeller Spring 2007 Motifs are Elementary Units of Cellular Networks As the molecular components of a speci c motif often interact with nodes that are outside the motif how the different motifs interact with each other needs to be addressed Empirical observations indicate that specific motif types aggregate to form large motif clusters For example in the E coltranscription regulatory network most motifs overlap generating distinct homologous motif clusters in which the specific motifs are no longer clearly separable As motifs are present in all of the real networks that have been examined so far it is likely that the aggregation of motifs into motif clusters is a general property of most real networks Hierarchy Organization of Topological Modules As the number of distinct sub raphs grows exponentially with the number of nodes that are int e subgraph the study of larger motifs is combinatorially unfeasible An alternative approach involves identifying groups of highly interconnected nodes or modules directly from the graph s topology anld correlating these topological entities with their potential functional ro e licated by the fact that at face value the o ularity seem to be contradictory Modules by definition imply that there are groups of nodes that are relatively isolated from the rest of the system However in a scalefree network hubs are in contact with a high fraction of nodes which makes the existence of relatively isolated modules unlikely Clustering and hubs naturally coexist however which indicates that topolo ical modules are not independent but combine to form a hierarc ical network I Z 0 o E m E m 3 r n U 8 r o 3 G O 3 00 BINF739 SolkaWeller Spring 2007 Hierarchy Organization of Topological Modules An example of such a hierarchical network is shown previously this network is simultaneously scalefree and has a high clustering coefficient that is independent of system size rk is made of many small highly integrated 4node modules that are assembled into lar er 16node modules each of which combines in a hierarchical ashion into even larger 64node modules The quantifiable signature of hierarchical modularity is the dependence of the clustering coefficient on the degree of the node This indicates that nodes with only a few links have a high Cand belong to highly interconnected small modules By contrisgttfhe highly 39 in i erent connected hubs have a lowC with their role being to l and othervwse not communicating modules It should be noted that the random and scalefree models that are shown preVIousl do not have a hierarchical topology because Ck is independent of in their case This is not surprising as their construction does not contain elements that would favor the emergence of modules Identifying Topological and Functional Modules Signatures of hierarchical modularity are present in all cellular networks that ave been investigated so far ranging from metabolic to protein ro ein interaction and regulatory networks But can the modules that are present in a cellular network be determined in an automated and objective fashion This would re uire a uni ue breakdown of the cellular network into a set of biologically relevant functional modules T e no news is that if there are clearly separated modules in the system most clustering metho s can i en i them Indeed several methods have recently been introduced to identify modules in various networks using either the network s topological description or combining the topology with integrated functional genomics data It must be kept in mind however that different methods predict different boundaries between modules that are not sharply separated This ambiguity is not only a limitation of the present clustering methods but it is a consequence of the network s hierarchical modularity BINF739 SolkaWeller Spring 2007 Identifying Topological and Functional Modules The hierarchical modularity indicates that modules do not have a characteristic size the network is as likely to be partitioned into a set of clusters of 10 20 components metabolites genes as into fewer but larger modules At resent there are no objective mathematical criteria for deciding that one partition is better than another Indeed in most of the present clustering algorithms some internal parameter controls the typical size of the uncovered smaller mo u es Does this mean that it is inherently impossible to identify the modules in a biological network From a mathematical pers ective it does indeed indicate that looking for a set of unique modules is an illde ne pro lem An easy solution however is to avoid seeking a breakdown into an absolute set of modules but rather to visualize the hierarchical relationship between modules of different sizes The identi cation of the groups of molecules of various sizes that together carry out a speci c cellular function is a key issue in network biology and one that is likely to witness much progress in the near future BINF739 SolkaWeller Spring 2007 40 Subgraphs Subgraphs A connected subgraph represents a su set of nodes that are connected to each other in a specific wiring diagram For example in part a ofthe figure four nodes that form a little square yellow represent a subgraph of a square lattice Networks with a more intricate wiring diagram can have various different subgraphs or exam e in part A of the figure in BOX 1 nodes A and C form atriangle subgrap whereas AB F and G form a square Examples of different potential stgraphs that are present in undirected networks are shown in part b of the figure a directed network is shown in par c It should be noted that the number of distinct subgraphs grows ex onentially with es an Increasing number 0 no Motifs Not all subgraphs occur with equal frequency Indeed the square lattice see figure part a contains many squares but no triangles In a complex network with an apparently random wiring diagram al subgraphs from I J are present H m m I I I I as motifs are over represented as compared to a ran omized version ofthe same network For example the directed triangle motifthat is known as the feedforward loop see figure top of part c emerges in bot transcriptionregulatory and neural networks whereas fourInode feedback loops see figure middle of part c represent characteristic motifs in electric circuits but not in biological systems To identify the motifs that characterize a given network all subgraphs ofn nodes in the network are determined Next the network is randomized while keeping the number of nodes links and the degree distribution unchanged Subgraphs that occur significantly more frequently in the real network as compared to randomized one are designated to be the motifs 41 Motif Clusters The motifs andJsubgraphs that occur in a b c of each other I E L i A A 39 il39 l i tili ilfi ifdi ii if t j i Cl li that are found in the Escherichia coli l r 1 ifii 39Llil Ll a39 ilfslT El As the figure shows 208 of the 209 hi fan motifs form two extended motif clusters RDo7rin et a manuscript in preparation and only one motif remains isolated bottom left corner Such clustering of motifs into motif clusters seems to be a general property of all real networks In part d of the figure the motifs that share inls with other motifs are shown in blue otherwise they are red The different colors and shapes of the nodes illustrate theirfunctional classification l Network Robustness A key feature of many complex systems is their robustness which refers to the system s ability to respond to changes in the external conditions or internal organization while maintaining relatively normal behavior To understand the cell s functional organization insights into the interplay between the network structure and robustness as well as their joint evolutionary origins are needed BINF739 SolkaWeller Spring 2007 42 Topological Robustness Intuition tells us that disabling a substantial number of nodes will result in an inevitable functional disinte ration of a networ This is certainly true for a random network if a critica fraction of nodes is removed a phase transition is observed breaking the network into tiny oncommunicating islands of nodes Complex systems from the cell to the Internet can be amazingly resilient against component failure withstanding even the incapacitation of many of their individual components and many changes in external conditions We have recently learnt that topology has an important role in generating this topological ro us ness Scalefree networks do not have a critical threshold for disintegration they are amazingly robust against accidental failures even if 80 of randoml selected nodes ai the remaining 20 still form a compact cluster with a pat connecting any two no es This is because random failure affects mainly the numerous small degree nodes the absence of whic oesn t disrupt the network s integrity This reliance on hubs on the other hand induces a socalled attack vulnerability the removal of a few key hubs splinters the system into small isolated node clusters BINF739 SolkaWeller Spring 2007 Topological Robustness This doubleedged feature of scalefree networks indicates that there is a strong relationship between the hub status of a molecule for example its number of links and its role in maintaining the viability andor growth of a cell Deletion analyses indicate that in 5 cerev sae only 10 of the proteins with less than 5 links are essential but this fraction increases to over 0 o for proteins with more than 15 interactions which indicates that the protein39s egree of connectedness has an important role in determining its deletion phenotype Furthermore onl N 187 of 5 cerev sae genes 144 in E mI are lethal when deleted in ividually and the simultaneous de etion of many E calgenes is without su s antia phenotypic e ect These results are in line with the expectation that many lightly connected nodes in a scalefree network do not have a major effect on the network s integr39ty The importance of hubs is further corroborated by their evolutionary consenation highly interacting 5 cerev sae proteins have a smaller evolutionary distance to their orthologues in Caenarhabd t s elegans and are more likely to have orthologues in higher organisms BINF739 SolkaWeller Spring 2007 43 Functional and Dynamic Robustness A complete understanding of network robustness requires that the functional and dynamic changes that are caused by perturbations are explored In a cellular network each node has a slightly different biological function and therefore the effect of a perturbation cannot depend on the node s degree only This is well illustrated by the finding that experimentally identified protein complexes tend to be composed of uniformly essential or non essential molecules This indicates that the functional role dispensability of the whole complex determines the deletion phenotype of the individual proteins BINF739 SolkaWeller Spring 2007 Functional and Dynamic Robustness The functional and dynamical robustness of cellular networks is supported by recent results that indicate that several relatively welldelineated extended aried perturbat39ons For examdple the c axis receptor module of E 039 maintains its normal function espite signi cant changes in a speci ed set of internal or external parameters which leaves its tumbling frequency relatively unchanged even under ordersof magnitude deviations in the rate constants or ligand concentra ions The development of the correct segment polarity attern in qusqphla n E meapagasterembwos is also robust to marked c anges in the initial conditions reaction parameters or o the a sence of certain gene pro uc s However similar to topological robustness dynamical and functional robustness d are also selective whereas some im ortant parameters remain unchange under perturbations others vaw WI ely For example theadaptation time or steadystate behavior in chemotaxis show strong variations in response to changes in protein concentrations BINF739 SolkaWeller Spring 2007 44 Functional and Dynamic Robustness Although our understanding of network robustness is far from complete a few h ve important emes a emerged First it is increasingly accepted that adaptation and robustness are inherent network properties an not a result of the finetuning o a component39s characteristics rid robustness is inevitably accompanied by vulnerabilities although man cellular networks are well adapted to compensate for the most common pertur tions they collapse when well selected network componenls are disrupted Third the abilit of a module to evolve also has a key role in developing or limitin robustness In eed evolutionarily frozen39 modules that are responsible for key ce uar functions such as nucleicacid synthesis might be less able to withstand uncommon errors suc as the inactivation of two molecules within t e same functional module Foexamleoro e 39 L g quot quot t tolerate further ene inactivation in the evolutionarily highly conserved pyrimidine metabolic modu e even in rich cultural media Finally modularity and robustness are resumably considerabl quite intertwined with the weak communication between me ules probably limiting t e effecls of local perturbations in cellular networks BINF739 SolkaWeller Spring 2007 Beyond Topology Characterizing the Links Despite their successes purely topology based approaches have 5 important intrinsic limitation For example the activity of the various metabolic reactions or regulatory interactions differs widely some are highly active under most growth conditions others switch on only under rare environmental circumstances Therefore an ultimate description of cellular networks requires that both the intensity that is strength and the temporal aspects of the interactions are con5idered Although so far we know little about the temporal aspects of the various cellular interactions recent results have shed light on how the strength of the interactions is organized in metabolic and genetic regulatory networks 45 Beyond Topology Characterizing the Links In metabolic networks the flux of a given metabolic reaction which represents the amount of substrate that is being converted to a product within a unit of time offers the best measure of interaction strength Metabolic flux balance approaches which allow the flux for each reaction to be calculated have recently significantly improved our ability to make quantifiable predictions on the relative importance of various reactions giving rise to experimentally testable hypotheses A striking feature of the flux distribution of E coI39is its overall heterogeneity reactions with flux that spans several orders of magnitude coexist under the same conditions This is captured by the flux distribution for E coI which follows a power law This indicates that most reactions have quite small fluxes coexisting with a few reactions with extremely high flux values Beyond Topology Characterizing the Links A similar pattern is observed when the strength of the various genetic regulatory interactions that are prOVIded by microarray datasets are investigate Capturing the degree to which each pair of genes is coexpressed that is aSSIgnin each pair a correlation coeffICIent or examining the local similarities in perturbed transcriptome profiles of 5 cerew5ae indicates t at the functional organization of genetic regulatory networks might also be highly uneven That is although most of them onl have weakcorrelations a few pairs show qUIte a Significant corre ation coeffICIent These highly correlated pairs probably correspond to direct regulatory and protein interactions This hypothesis issupported by the finding that the correlations are higher along the links of the protein interaction network or between proteins that occur in the samecomplex as compared to pairs of proteins that are not known to interact directly 46 Beyond Topology Characterizing the Links Taken together these results indicate that the biochemical activity in both the metabolic and genetic networ 39 dominated by several hot links that represent high activity interactions that are embedded into a web of less active interactions This attribute does not seem to be a unique feature of biological s stems there are hot links in many non biological networks their activity following a wide distribution The ori in of this seemingly universal property of the links is probab y rooted again in the network topolo y Indeed it seems that the metabolic uxes and the weights 0 Inks in some non biological systems are uniquely determined by the scale free nature of the network topology At present a more general principle that could explain the coexpression distribution data equally well is lacking Future Directions Despite the significant advances in the past few years molecular network biology is only in its infancy Future progress is expected in many directions ranging from the development of new theoretical methods to characterize the network topology to insights into the dynamics of motif clusters and biological function Most importantly to move significantly beyond our present level of knowledge we need to enhance our data collection abilities This will require the development of highly sensitive tools for identifying and quantifying the concentrations fluxes and interactions of various types of molecules at high resolution both in space and time In the absence of such comprehensive data sets whole arrays of functionally important cellular networks remain completely unexplored ranging from signalling networks to the role ofmicroRNAS in network topology and dynamics 47 Structure and Representation BINl739 SPRING2007 Jeff Solka and Jennifer Weller Structure and Representation BINF739 SolkaWeller BINF739 Acknowledgement Unless otherwise noted all figures in this lecture have been adapted from Gross and Yellen Graph 777603 anthsAppica on Chapman and HallCRC Press 2006 Structure and Representation BINF739 SolkaWeller BINF739 Introduction The structure of a graph is what characterizes a graph that is independent of its representation A graph can have many representations Incidence table Drawings When are two graphs structurally equivalent isomorphism problem Incidence matrix and adjacency matrix allow use to utilize vector space mathematics Addition and deletion of nodes and edges on graphs become similar in scope to the elementary row operations that we find in linear algebra Structure and Representation BINF739 SolkaWeller BINH39 21 Graph Isomorphism Structurally Equivalent Graphs How do we know that these two graphs are the same Figure 211 Twn ili L Iint drawings 139er same graph Structure and Representation BINF739 SolkaWeller BINH39 21 Graph Isomorphism Structurally Equivalent Graphs What if the edges are labeled differently from one graph to another or not at all There in lies the rub r 2 4 a G H 6 5 7 8 Figure 212 Two drawings f mpnriauy thr same grapu Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism 1 2 5 r 4 3 G l I u H wok yd 0 6 5 f 7 B Figure 242 Twu rh uiug ul39uswulinlly hl39 samn graph Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Formalizing Structural Equivalence for Simple Graphs Def Leg Gand Hbe two simple graphs A vertex bijection f 5 9 lH preserves adjacency if for every pair of adjacent vertices uand Iin graph G the vertices fuand fIare adjacent in graph H Similarly fpreserves nonadjacency if fuand fIare nonadjacent whenever uand Iare non adjacent Def A vertex bijection 39 5 9 lH between the vertexsets of two simple graphs G and H is structurepreserving if it preserves adjacency and nonadjacency That is for every paif of vertices in G u and v are adjacent in G cgt f u and f v are adjacent in H Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Formalizing Structural Equivalence for Simple Graphs Def Two simple graphs G andH are 1W denoted G E H if there exists a structurepreserving vertex bijectionf1VG gt VH Such a functionf between the vertexsets of G and H is called an isomorphism from G to H Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Formalizing Structural Equivalence for Simple Graphs allD mm d73 wig ll15 ei4 gl6 hll7 n iulplg graphs o 1 3 2 5 4 a 7 Figure 214 Autilljm Wu ul ilvpiuring 1m isnnmi39lihisul Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Formalizing Structural Equivalence for Simple Graphs 1 2 5 5 gt O H ia 4 7 Figure 215 Hijt wtiVC and mljmwlu39yqn rlsm39viug but nul an isomorphism Figure 216 Preserves zuljal39mn y and mInmljavmuy but is not bijtvtiveu Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Extending the De nition of Isomorphism to General Graphs Does this mapping preserve adjacency and nonadjacency Are these two graphs structurally equivalent Figure 217 391 Wu graphs that dI39l uni structurally xquimlrnt Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Extending the Definition of Isomorphism to General Graphs Def A vertex bijection f Ig 9 IH between the vertexsets of two graphs Gand H simple or general is structure preserving if 1 The number of edges even if 0 between every pair of distinct vertices uand vin graph Gequals the number of edges between their images fu and 171 in graph H and 2 The number of selfloops at each vertex xin Gequals the number of selfloops at the vertex fX in H Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Specifying an Isomorphism Between Graphs Having MultiEdges Def Let Gand Hbe two isomorphic graphs A vertex bijection fy lG amp VH and an edge bijection f5 EG amp EH are consistent if to every edge e in Ea the function fy maps the endpoints of eto the endpoints of edge 12029 A consistent mapping pair fy lG amp lH f5 EG amp 5 is often written shorthand as f G amp H Prop 211 Let Gand Hbe any two graphs Then Gis isomorphic iff there is a vertex bijection fy lG amp VH and an edge bijection 1 EG amp EH that are consistent Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism m ii i i Ii I and 391 ms nili iiiiiIiuliu lliPH sin isumtuphiam iruiii i i w m x minnun i i a m m m minii M Li a LH iiiai 41ifquotil ni Figure 218 Thwn are 1392 i lilil39l igtltxllnl39ligtll1 fruln 4 in H Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Isomorphic Graph Pairs Thm 212 Let Gand Hbe isomorphic graphs The they have the same number of vertices and the same number of edges Thm 213 Let f G amp Hbe a graph isomorphism and let 1 be in iG then degfv degv Cor 214 Let Gand Hbe isomorphic graphs Then they have the same degree sequence Cor 215 Let f G amp Hne a graph isomorphism and let e be in E6 Then the endpoints of edge fe have the same degrees as the endpoints of e Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Isomorphic Graph Pairs Figure 215 Hypmw39ulm graph o anil cirrllliu lmldm39 2 m isolnurpliir i wiiink Vlli AII39J39IH39HS ladder l h u graph ulnamnl irum Ihv eru uirn39 ime in 391 ili39iii wiiiiill39 cirr nlzn l iiri39i 139v gtiVHl fiI I HlWHil ig NNHquot iwplaku vm mil innum Ilnl rm imit ii liir ii39 r Killinwiilh 0 0 2 4 T V1 I V 3 L i K i 3 5 a X 39 K33 ML3 Figure 2110 Bipzu tito graph IL 1 and D I bius ladder H i are isoulm phir Structure and Representation BINF739 SolkaWeller BINF739 21 Graph Isomorphism Isomorphism Type of a Graph Def Each equivalence class under 2 is isomorphic to is called an isomorphism type 33977 Figure 2111 Th four ismnurpluism tylu fur a ailnplf39 BVerlex graph Structure and Representation BINH39 SolkaWeller BINH39 21 Graph Isomorphism Isomorphism of Digraphs 1HHH 39 H ilxqrnplix my islt39zniurphilt39l llrvrr hull iwlnnilnwf l39u39Hnn ll14ll mailwrlyvn mplh vlml HVN rv Ih lll39v39l39llvlll ml Hu39h wigv HM r I139 lquotll rum HIM ll ilI lHlll 1391rllxleivlFirmlyHui va 39r r R I 039 Figure 2112 Fumr nun inmunphir ligrapllsl Structure and Representation BINH39 SolkaWeller BINH39 21 Graph Isomorphism The Isomorphism Problem in l lzl iu Ilw glulpll iwIllnrplliuu pl39uhltln lx lw Illlill i lnili until lHlllullllll lll l hlli39ill 2w u llirznmxzx lquot v my my will yumu h lnh llri39mnl lmwm 1mm MW rim w mumlim u h v wrumnmnui n y l lerul39h ll Structure and Representation BINF739 SolkaWeller BINF739 22 Automorphisms and Symmetry Def An isomorphism from a graph G to itself is called an automorphism Thus an automorphism p of a graph G is a structure preserving permutation on the vertex set of 6 along with a consistent permutation 75 on the edgeset of of G We may write 7r 71 7r Structure and Representation BINF739 SolkaWeller BINF739 22 Automorphisms ancl Symmetry Permutations and Cycle Notation Example 221 111 PH HHHEEHHII 7 Structure and Representation BINF739 SolkaWeller BINF739 22 Automorphisms ancl Symmetry Geometric Symmetry Examp1 222 Hi gi39aiili 1H ms at mmnuiminim 1 ii ur mom i in iiizaim 1 d ruluiwn m rvlivr39iiim ni iin iiri39 lnj in Via iI 7 I I K14 has 4 vertices jg hence there w v should be 4 24 mm mm permutations but W39W W41 node x must be H iili l iIi ry 7 wl39liiiii ai Ii Fi is39i39ii39liii ii xed ir39iiiiiiif ulir39iiit Hm MHLHr Hence there are lL U rvIalinii iJiin 1 iii in ir oi 3 or 6 39JJLIV i39n iii liim ij riin u M i iquot fil i39r il39il ii u if ii 1 Ii r w viiJ r permUtatlons rvii iliru f iJ tiitV Ii i H ui iMiu i1 roii iliru r iJ39iiii jiH r ir39iiii M Structure and Representation BINF739 SolkaWeller BINF739 11 22 Automorphisms and Symmetry Geometric Symmetry Automorphisms 3910t3345678 Al 8M2 73156 32 30 54 07 1I 8N1 73 54 6 Figure 222 A graph willi l39rmr automorphisms Structure and Representation BINF739 SolkaWeller BINH39 22 Automorphisms and Symmetry Limitations of Geometric Symmetry mum i i w x II JIHE Hliuiii win Structure and Representation BINF739 SolkaWeller BINH39 12 22 Automorphisms and Symmetry Limitations of Geometric Symmetry Def A graph G is vertextransitive if for every vertex pair u V in V0 there is an automorphism that maps uto Def A graph Gis edgetransitive if for every edge pair 0 ein E67 there is an automorphism that maps 0 to e i if h n quotw Kenny mm n edgetransitive not vertex transitive why edgetransitive and vertextransitive LTR Structure and Representation BINH39 SolkaWeller BINH39 I 22 Automorphisms and Symmetry Limitations of Geometric Symmetry Figure126 Th Pquot quot quot Kml l Figure 224 Th t il39l39lllani graph mum i 3i V and ET V and ET Structure and Representation BINH39 SolkaWeller BINH39 13 22 Automorphisms and Symmetry Vertex Orbits and Edge Orbits Def The equivalence classes of the vertices of a graph under the action of the automorphisms are called vertex orbits The equivalence classes of the edges are called edge orbits Thm 221 All vertices in the same orbit have the same degree mnx mlmw mlle Hal Automorphisms Thm 222 Alledges in the same lo13l3l45l107W orbit have the same pair of degrees Wu 8 monitors at their endpoints Azzmmu be slow 140 8 7N3 W 6 Automorphism theory lies at the Figumz m C l1mIEmmpk223 intersection of graph theory and group theory chpt 14 and chpt Structure and RepPelsentation BINF739 SolkaWeller BINl739 22 Automorphisms and Symmetry How to Find Orbits It is not known whether there is a polynomialtime algorithm for nding orbits ll lm w l mu In Hwywk n1 mura 2 3 v M i lr39 u l mmml on i ll Tr nH HHH Ullll rlll39z mnlxlls 11ml rrupuilrlinl lwmmr willl r wriiws I upl l Vil39lillilif 1 llv l5 lameml wrllih arr 0 3 2 Fianna 226 Find the vortex nrhiis and lhr alga orbits Structure and Representation BINF739 SolkaWeller BINl739 2 3 Subgraphs Def subgraph ofa graph Gis a graph Hwhose ver ces and edges are all 39n 5 1f His a ilbgraph of s we may also say fhat Gis a supergraph of H Def 7 A ilbdigraph of a digraph Gis a digraph H whose vertices a1d arcs are all In 6 Def 7 A proper subsetHof Gis a ilbgraph such fhat VH is a proper subset of v5 or 5 is a proper subset of 55 Sunny 2rd REVexenhhm Emma sdkaMeHuExmza 2 Subgraphs i am who manhurhrrrrrrrrwhhw m r Sunny 2rd REVexenhhm Emma sdkaMeHuExmza 23 Subgraphs A Broader Use of the Term Subgraph The usual meaning of the phrase His a subgraph of Gquot is that H is merely isomorphic to a subgraph of G K 00 D a G 82 D3 K3 Figure 232 A graph null mum of iis subgraphs Sn39ucture and Reprsentation BINF739 SolkaWeller BINF739 23 Subgraphs Spanning Subgraphs Def Asubgraph His said to span a graph Gis VH VG Sn39ucture and Reprsentation BINF739 SolkaWeller BINF739 23 Subgraphs Spanning Subgraphs Def A spanning tree of a graph is a spanning subgraph ihat is a wee Figure233 A spanning nco Re resermauon BINF739 SolKaWeller BINF739 23 Subgraphs Spanning Subgraphs Prop 231 A graph Gis connected iff it coniains a spanning tree Prop 232 Evew acyclic subgraph ofa connected graph G is coniained in at last one spanning tree of G Def An acyclic graph is called a forest Simone and Represermuon BINF739 SolKaWeller BINF739 23 Subgraphs Spanning Subgraphs G Ew Figure 234 A spanning flumt 1739 of graph 1 Structure and Representation BINF739 SolkaWeller BINF739 23 Subgraphs Cliques and Independent Sets Def A subset of 5 is called a clique if every pair of vertices in Sis joined by at least one edge and no proper superset of has this property NB Sometimes this property is defined without the maximality condition Def The clique number of a graph Gis the number aG of vertices in the largest clique in G x l V Z Figure 235 A graph will three cliques Structure and Representation BINF739 SolkaWeller BINF739 23 Subgraphs Cliques and Independent Sets Def A subset 50f 6 is said to be an independent set if no pairs of vertices in S is joined by an edge That is Sis a subset of mutually nonadjacent vertices of G Def The independence number of a graph Gis the number 056 of vertices in a largest independent set in G Structure and Representation BINF739 SolkaWeller BINl739 23 Subgraphs Induced Subgraphs Def For a given graph G the subgraph induced on a vertex subset Uof I67 denoted GU is a subgraph of G whose vertexset is U and whose edgeset consists of all edges in Gthat have both endpoints in U That is VGW U and EGW ee EG lendpts e Q U c C I u h 1 U l a LN a a g d a induced on u v Figure 236 A subgraph indiumd on a subset of vm39 i39r s Structure and Representation BINF739 SolkaWeller BINl739 23 Subgraphs Def For a given graph G the subgraph induced on an edge subset Dof Ea denoted 60 is the subgraph of Gwhose edgeset is Dand whose vertexset consists of all vertices that are incident with at least one edge in D That is VGUDgt ve VG Ive endptse for some ee D andEGD D 77 JW induced on a c Figure 237 A uhgraph induvml in x sulmr ul39 xlgns Structure and Representation BINF739 SolkaWeller BINF739 23 Subgraphs Induced Subgraphs Def The center of a graph G denoted ZG is the subgraph induced on the set of central vertices of G Figure 238 A graph 39huhr cvutm is i 14 y1 lcn Structure and Representation BINF739 SolkaWeller BINF739 20 23 Subgraphs Local Subgraphs Def The open local subgraph or open neighborhood subgraph of a vertex v is the subgraph LV induced on the neighbors of v J U 2c 3 7V V G 4 l quot 39 l W 1 Q M 1quot HVL 39 g LW7 I l l l a y l LlLIl LW 1 LlWl Figure 239 A graph t ziml rlmw of its lumil subgraphs Structure and Representation BINF739 SolkaWeller BINF739 23 Subgraphs Local Subgraphs Def Thm 233 Let f G 9 Hbe a graph isomorphism and u be in V6 Then fmaps the local subgraph Lu ofg isomorphically to the local subgraph Lfu of H 7 lG Figure 2110 Iwu 1 Pgulm BVFrlex graphs The local subgraphs for graph G are all isomorphic to 4K1The local subgraphs for graph H are all isomorphic to P3 Hence the two graphs are not isomorphic Also we note xG 4 but xH 2 and 036 2 but 03H 3 Structure and Representation BINF739 SolkaWeller BINF739 21 I 23 Subgraphs Def A component of a graph Gis a maximal connected subgraph of G In other words a connected subgraph H is a component of Gif H is not a proper subgraph of any connected subgraph of G p Vxo Figure 2311 A graph with four A39mupuueurs Def In a graph the component of a vertex v denoted Cv is the subgraph induced by the subset of all vertices reachable from M Structure and Representation BINF739 SolkaWeller BINF739 I 24 Some Graph Operations Deleting Vertices or Edges Def If vis a vertex of a graph G then the vertexdeletion subgraph G v is the subgraph induced by the vertex set lG v Def If eis an edge of a graph G then the edgedeletion subgraph G eis the subgraph induced by the edgeset EG e Structure and Representation BINF739 SolkaWeller BINF739 22 24 Some Graph Operations Deleting Vertices or Edges Gw w Flgure241 nw nmu yr ilr39loliug thv gmx u rm graph 1 v w Figure 242 TLu rmxlt deeltllng the edge I from graph H Structure and Representation BINF739 SolkaWeller BINF739 24 Some Graph Operations Network Vulnerability Def A vertexcut in a graph Gis a vertexset Usuch that G Uhas more components than 6 A cutvertex or cutpoint is a vertexcut consisting of a single vertex Figure 243 A grayl lrlx four I lll i39l39ll1391 Structure and Representation BINF739 SolkaWeller BINF739 23 24 Some Graph Operations Network Vulnerability Def An edgecut in a graph Gis a set of edges D such that GD has more component than G Def A cutedge or bridge is an edgecut consisting of a single edge D r s a f c Figure 244 A graph i39h lln39m rill mlgvs Structure and Representation BINF739 SolkaWeller BINF739 24 Some Graph Operations Network Vulnerability Def An edge of a graph is called a cycleedge if e lies in some cycle or the graph Prop 241 Let ebe an edge of a connected graph G Then G e is connected iff e is a cycleedge of G Prop 242 An edge of a graph is a cutedge iff it is not a cycleedge Structure and Representation BINF739 SolkaWeller BINF739 24 24 Some Graph Operations The GraphReconstruction Problem Def Let Gbe a graph with lG V1 V2 14 Then the vertexdeletion subgraph list of Gis the list of the subgraphs GVJ GI7 The reconstruction deck of a graph is its vertexdeletion subgraph list with no labels on the vertices We regard each individual vertexdeletion subgraph as being a card in the deck Structure and Representation BINF739 SolkaWeller BINF739 24 Some Graph Operations The GraphReconstruction Problem mgmm Gx Gy g Gv Figure 245 A graph and its vvriPX uliloliuu subgrth 1m Structure and Representation BINF739 SolkaWeller BINF739 25 24 Some Graph Operations The GraphReconstruction Problem Def The graphreconstruction problem is to decide whether two nonisomorphic graphs with three or more vertices can have the same reconstruction deck N B For unlabeled graphs this is one of th foremost unsolved problems in graph theory Figure 247 151i lll39 unly graph with this l3939439ULH IU39lirill 10139le Structure and Representation BINF739 SolkaWeller BINF739 I 24 Some Graph Operations Adding Edges or Vertices Def Adding an edge between two vertices uand wof a graph G means creating a supergraph denoted G U e with vertexset lGand edgeset 55 U e where e is a new edge with endpoints uand w v v c y 393 if h i i39L 5 JW Figure 243 lltlill uu mlgiw with x liillnriHH u runl ii Structure and Representation BINF739 SolkaWeller BINF739 26 I 24 Some Graph Operations Adding Edges or Vertices Def Adding a vertex to a graph G where ViS a new vertex not already in V6 means creating a supergraph denoted G U V with vertexset VG U V and edge set E8 Structure and Representation BINF739 SoikaWeiier BINF739 39 I 24 Some Graph Operations Graph Union Def The graph union of two graphs 6 V Eand G39 V E is the graph GU G39whose vertexset and edgeset are the disjoint unions respectively of the vertex sets and edgesets of Sand 639 Q L Figure 249 Tim graph Huiun K i i 1 nl iin mpivs of I Structure and Representation BINF739 SoikaWeiier BINF739 24 Some Graph Operations Joining a Vertex to a Graph Def Ifa new vertex Visjoined to each of the pre existing vertices of a graph G then the resulting graph is called thejoin of Vto Gor the suspension of Gfrom V and is denoted G V Figure 2410 391 hi Lulml llr li 1 Stmcture and Representation BINF739 SolkaWeller BINW39 24 Some Graph Operations Edge Complementation Der Let G be a simple graph Its edgecomplement or complement Gis the graph crime same vertex set such that two vertices are adjacent in G ill the are not adjacent in G Figurez412 A graph and il A39mnplt39lnt ni Stmcture and Representation BINF739 SolkaWeller BINW39 28 25 Tests for NonIsomorphisms Def A graph invariant or digraph invariant is a property of graphs digraphs that is preserved by isomorphism Some examples of such properties include number of vertices the number of edges and the degree sequence Thm 251 Let f G 9 Hbe a graph isomorphism and let Vbe in V5 Then the multiset of degrees of the neighbors of vequals the multiset of degrees of the neighbors of fv Structure and Representation BINl739 SolkaWeller BINF739 25 Tests for NonIsomorphisms A Local Invariant 9 o LV o o o H7 lieg G H Figure 251 miwumrplriv grilplh with lln smur itgrew nunmm J x y r l Figure 252 Nonismnurpliiu digraphs with mmrrmr doger gt i1iiCli439v Structure and Representation BINl739 SolkaWeller BINF739 29 25 Tests for NonIsomorphisms Distance Invariants Thm 252 The isomorphic image of a graph walk is a walk of the same length l 39 5 i 5 s 0 y 2 D 3 Ai e 7 V CLi 5 ML4 3 3 Figure 253 Non ibnuinrpllil graphs with llu same degree szqmmu ii iii viiHim iniim liiiiiiilli i lxiilirill L immun i39llsliillii v nri in mm 1mm llii 39l w h 73915 39v l lv 1mm ii 1 iliui may ilu ii 1 ml j gt7 1 l mm 7 unmixin mummilhlaniw from ivl39hx ii in i 1i is 1 for wry1 I llir nm in n m illi h 2 Thu lllr m w erpim xr um ul 4 1 mi nii n Structure and Representation BINF739 SolkaWeller BINW39 25 Tests for NonIsomorphisms Subgraph Presence Thm 256 For each graphisomorphic type the number of distinct subgraphs in a graph having that isomorphism type is a E graph invariant EVilllpll39 27 39 Tlu ii arriixlw ill l39lgill39v 393 Ti lfll quot ill 1 l vL llIrll39 nvu iliuuuli Ilur rip imi i quv Iii lu im h inurl I 39 lisiw Im Ix will quot ill invl l hfl llli lllh lliuii39 Ill Z 3 llll3939quotli39il ll 4 i Hi r39 1 4mm l Ir 1 Tiaivy inn 1mm lilm mi lumilim ii i aeaoo Figure 254 Fivr mutually mmismnurphir Svvrlnx Sammilar graphs 39iiillhl x ww Inn vvlwvxi ilmx amp iml i39 39Il I39M iiil39v imlr viili lllr mm mm iii lmw llli rilllil v mnlrl ilmnmmli ilu pm In Him ruin ilml Hi ii 7 l s 1 39i 1i Structure and Representation BINF739 SolkaWeller BINW39 30 25 Tests for NonIsomorphisms Edge Complementation Thm 257 Let G and H both be simple graphs They are isomorphic iff their edgecomplements are isomorphic Example 256 umi miir i vmpimnm ni iiw E iluiirisi39iiiurpilii iiir urignmi 1mm mm in u u m i Hinw ihx i nunriiiih39 Figure 255 Two I39I iativt ly ult uxv mmimmrpmr 5 rvgtnlzu39 graphs Structure and Representation BINF739 SolkaWeller BINF739 25 Tests for NonIsomorphisms Table 251 Sume graph invariants I Hi mimlnrni quotquoti39lii39i 1 Th iniimiyrHIVrum I luv xlv grim rqiiwim 1 lil39 inliilisfi nilMn lirzi 3 Hi 21 v x ul39 nriuiiimrs u a i39nrr39ml Inuir39lz i Humv iri39 rmiin girila T m I i w39v uvlmiur wiiqur immimr 39 lur um IMHgtHJV Hulxurnirlr illt Hulnlwr ml Thaiva mp1 391 i 39139 s mmu uriph Iii quot7i2 1 gtl 39lil ilHIIKH Structure and Representation BINF739 SolkaWeller BINF739 31 26 Matrix Representations r Adiacency Matrices 1Inplut2G1 lieurv quot39 2i i Hm 111v uljm39vm39y Imitrix Ufa simplv graph I 1 HM 1u i iiil39 in Inziirn how rmx liiil l Hlllllllh 1r lmlh mxi xvi In pinupmi rrvlermua if 1 1 um i ii M Hllil I am ivlim39riii I i n ll i uiinru39lu ii i hu Ih Iil24quot ll 39 muiri vi 1 L39Y39Liiii u iill r1 5pm In rlr uriirrmu u a ir yg U H i I I u n 1 n W x y 1 Ii H xquot 39 1 i i n v r U I i ii Figure 261 A graph and ils adjacency matrix Structure and Representation BINF739 SolkaWeller BINF739 26 Matrix Representations Adjacency Matrices Prop 261 Let Gbe a graph with adjacency matrix AG Then the value of element A GuVof the rth power of matrix AG equals the number of uVwalks of length r mimiiux lip ml Iuv mnlrix nl39a siLupIr graph n i mm L is i H39Mii39n MW my rinmu w mi my ml in lwliljirli hr Hi i w rim 1M 7 W i ii iiu iv if Mil n4 u mr n iiilivihhw l xmuplv 213 hr min um in mm mi ihw Jumpii Hi I iliilr 391 ii 391 uw lip ii iiv mm H u I u l u y M ii I ii ii w X 7 n i n 1 n I I i i u u i i V i n n Figure 262 A digraph and in mijmnmy umtrix Structure and Representation BINF739 SolkaWeller BINF739 32 26 Matrix Representations Adjacency Matrices pi ulHJsil inn 397 Iv 1 in riigmpli uiiii Mi ii it iiir riumwuisui39um i Ui iliv Ailll39lii incirrix 39 iii illil Hl39iiii39 vi Proposition 263 ii iquot In a Jigrzipii nil u quotiwiigi INCH w Iii vniri i ii i mi rliv 1 mi unin quot 17quot L i Structure and Representation BINF739 SolkaWeller BINF739 ip vijniij ii Huhpg Miniii I Illr3912 ni iiiNIH 1i rrliixili1u 111 11 Hi39 i iiv i a lien iliv Iilii zi Iliiii i iw i T wi matrix i 1 i1iil i i39 Humw I39iil iliil39i l39ii n7 r I39Vz 13911 I v in iv 26 Matrix Representations BruteForceGraphIsomorphismTesting Under the orderinqs u V w xand a d c b u v ii ii i i I i i ii i n u i i u X w I i ii i ii a b ii i i ii i ii I i i in Figure 263 Eurannual isnlmn39phiuu dug ailim39bury manam Structure and Representation BINF739 SolkaWeller BINF739 33 26 Matrix Representations BruteForceGraphIsomorphismTesting Algorithm 251 Brurmxurr mt fm39 grale rwmmphism Li min 1 mini H J in mm Irquot u Vii iii riihhli in 39i iirwr39 i r rwinwrpin in i Ii iini i i ni viliiii Vi w Av Hliiviii i39h ur rm minim iii Mr M mir urri mm iri L iriirii Ir i riir I r ivi i rr rim vii39ii l39iiiE in M ruinmm n HAHN L n rum i Structure and Representation BINF739 SolkaWeller BINF739 26 Matrix Representations Incidence Matrices for Undirected Graphs Def The incidence matrix for a graph Gis the matrix 6 whose rows and columns are indexed by some ordering of VG and ES respectively such that Iii iii i irni m r rwirwim Mir iii 1 iii i m r n irrr mi mi 139 ii r 1 it wilri wry ili Structure and Representation BINF739 SolkaWeller BINF739 34 26 Matrix Representations Incidence Matrices for Undirected Graphs Figure 264 A grnpll and its incidente matrix Structure and Representation BINF739 SolkaWeller BINF739 26 Matrix Representations Incidence Matrices for Undirected Graphs Prop 264 The sum of the entries in the row incidence matrix is the degree of the corresponding vertex Prop 265 The sum of the entries in any column of an incidence matrix is equal to 2 Structure and Representation BINF739 SolkaWeller BINF739 I 26 Matrix Representations Incidence Matrix for Digraphs Def The incidence matrix for a digraph D is the matrix IG whose rows and columns are indexed by some ordering of V0 and ED respectively such that 7 iii gt ili livrr39i U1quot Hiquot393 17 ii is iiuinilwi39r 391 li39 1e 3i illimqi ii I Inlil39l wii i 39il 17i 1 quot1t Structure and Representation BINF739 SolkaWeller BINF739 I 26 Matrix Representations Incidence Matrix for Digraphs i A i ii 0 i I l i quot 5 b 1 l39 i ii i ii ii ii ii I i J j M ii ii 7i ii I 9 X 39 Figure 255 A digraph and ii inrideuco mann Structure and Representation BINF739 SolkaWeller BINF739 I 26 Matrix Representations Table of Incident Edges a More Efficient Storage Strategy v Strccture and Representation BINF739 SoikaWeiier BINF739 26 Matrix Representations Comparing the storage requirements of the three storage strategies Incidence matrix OV E Adjacency matrix OV2 Table of incident edges O El Strccture and Representation BINF739 SoikaWeiier BINF739 Using David Marchette graph Package in R J L Solka and Jennifer Weller jlsoDiaQZgnail oomjwellerg mLL ed u GMU Agenda I Installing the package Installation I Obtain Package from the Course Website or Via Email I Under Linux We Execute at the Command Line I R CMD INSTALL graph03230targz BINF739 SPGO7 p31l Our First Graph I librarygraph I gpetersen I plotg BINF739 SPGO7 p41l The Circulant Graph I librarygraph I gcirculantn13CC15 I plotg From an Adjaceny Matrix to a Graph gadj matrixc0110101011010010 ncol 4 byrowTRUE g asgraphgadj P0tg BINF739 SPGO7 p61l From an Adjaceny Matrix to a DiGraph ADg matrixc0100101010010000ncol4 byrowTRUE g asdigraphADg p0tg devprintpostscriptfile PICSmydigraphps BINF739 SPGO7 p71l The Bipartite Graph K473 plotk34mode bipartite parts c1111222 The Cube g cube P0tg BINF739 SPGO7 p91l The Cube g whee8 P0tg yu se 0 V g BINF739 SPGO7 p101l geodesicdist Description Find the geodesic distances between all pairs of vertices Usage geodesicdistg Arguments g A graph M a matrix of geodesic distances BINF739 SPGO7 p111l Extracting the Adjacency Matrix gadj matrixc0110101011010010 ncol 4 byrowTRUE g asgraphgadj gadj 1 111211 3114 1 0 1 1 0 2 1 0 1 0 3 1 1 0 1 4 0 0 1 0 gnewadj adjacencymatrixg gnewadj BINF739 SPGO7 p121l cliquenumber Description finds the size of the maximum clique in the graph Usage cliquenumberg U size0m0 Arguments g a graph Usizem only used by the recursion M returns the size of the maximum clique This can be 1 or 2 so technically this should be checked if one is pedantic about the definition of clique BINF739 SPGO7 p131l incidencematrix Description Extract the incidence matrix from an object of class graph Usage incidencematrixg Arguments g a graph object M the incidence matrix BINF739 SPGO7 p141l intervalgraph Description an interval graph defined by a matrix of intervals Usage intervalgraphintervals Arguments intervals An n by 2 matrix of intervals Each row corresponds to the endpoints of the interval M a graph BINF739 SPGO7 p151l

### 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!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

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