Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·March 28, 2012 12:27:10 PMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E4.2 DIRECTED GRAPHS‣digraph API‣digraph search‣topological sort‣strong componentsDigraph. Set of vertices connected pairwise by directed edges.2Directed graphsdirectedcycledirected pathfrom 0 to 2vertex of outdegree 4 and indegree 23Road networkVertex = intersection; edge = one-way street.AddressHolland TunnelNew York, NY 10013©2008 Google - Map data ©2008 Sanborn, NAVTEQ™ - Terms of UseTo see all the details that are visible on the screen,use the"Print" link next to the map.Vertex = political blog; edge = link.4Political blogosphere graphThe Political Blogosphere and the 2004 U.S. Election: Divided They Blog, Adamic and Glance, 2005Figure 1: Community structure of political blogs (expanded set), shown using utilizing a GEMlayout [11] in the GUESS[3] visualization and analysis tool. The colors reflect political orientation,red for conservative, and blue for liberal. Orange links go from liberal to conservative, and purpleones from conservative to liberal. The size of each blog reflects the number of other blogs that linkto it.longer existed, or had moved to a different location. When looking at the front page of a blog we didnot make a distinction between blog references made in blogrolls (blogroll links) from those madein posts (post citations). This had the disadvantage of not differentiating between blogs that wereactively mentioned in a post on that day, from blogroll links that remain static over many weeks [10].Since posts usually contain sparse references to other blogs, and blogrolls usually contain dozens ofblogs, we assumed that the network obtained by crawling the front page of each blog would stronglyreflect blogroll links. 479 blogs had blogrolls through blogrolling.com, while many others simplymaintained a list of links to their favorite blogs. We did not include blogrolls placed on a secondarypage.We constructed a citation network by identifying whether a URL present on the page of one blogreferences another political blog. We called a link found anywhere on a blog’s page, a “page link” todistinguish it from a “post citation”, a link to another blog that occur s strictly within a post. Figure 1shows the unmistakable division between the liberal and conservative political (blogo)spheres. Infact, 91% of the links originating within either the conservative or liberal communities stay withinthat community. An effect that may not be as apparent from the visualization is that even thoughwe started with a balanced set of blogs, conservative blogs show a greater tendency to link. 84%of conservative blogs link to at least one other blog, and 82% receive a link. In contrast, 74% ofliberal blogs link to another blog, while only 67% are linked to by another blog. So overall, we see aslightly higher tendency for conservative blogs to link. Liberal blogs linked to 13.6 blogs on average,while conservative blogs linked to an average of 15.1, and this difference is almost entirely due tothe higher proportion of liberal blogs with no links at all.Although liberal blogs may not link as generously on average, the most popular liberal blogs,Daily Kos and Eschaton (atrios.blogspot.com), had 338 and 264 links from our single-day snapshot4Vertex = bank; edge = overnight loan.5Overnight interbank loan graphThe Topology of the Federal Funds Market, Bech and Atalay, 2008GSCCGWCCTendrilDCGOUTGIN!"#$%& '( !&)&%*+ ,$-). -&/01%2 ,1% 3&4/&56&% 7'8 799:; <=>> ? #"*-/ 0&*2+@ A1--&A/&) A1541-&-/8B> ? )".A1--&A/&) A1541-&-/8 <3>> ? #"*-/ ./%1-#+@ A1--&A/&) A1541-&-/8 <CD ? #"*-/ "-EA1541-&-/8<FGH ? #"*-/ 1$/E A1541-&-/; F- /I". )*@ /I&%& 0&%& JK -1)&. "- /I& <3>>8 L9L -1)&. "- /I& <CD8 :K-1)&. "- <FGH8 J9 -1)&. "- /I& /&-)%"+. *-) 7 -1)&. "- * )".A1--&A /&) A1541-&-/;!"#$%&%'$( HI& -1)&. 1, * -&/01%2 A*- 6& 4*%/"/"1-&) "-/1 * A1++&A/"1- 1, )".M1"-/ .&/. A*++&) )".A1--&A/&)A1541-&-/.8 !!!"#"!!!!!"; HI& -1)&. 0"/I"- &*AI )".A1--&A/&) A1541-&-/ )1 -1/ I*N& +"-2. /1 1% ,%15-1)&. "- *-@ 1/I&% A1541-&-/8 ";&;8 #!"# $"# !$# ""$" $!!!!" % $ $!!!!!"& # ' ", % (# %!; HI& A1541-&-/0"/I /I& +*%#&./ -$56&% 1, -1 ) &. ". %&,&%%&) /1 *. /I& )%*$& +"*,-. /'$$"/&"0 /'12'$"$& O<=>>P; C- 1/I&%01%).8 /I& <=>> ". /I& +*%#&./ A1541-&-/ 1, /I& -&/01%2 "- 0I"AI *++ -1)&. A1--&A/ /1 &*AI 1/I&% N"*$-)"%&A/&) 4*/I.; HI& %&5*"-"-# )".A1--&A/&) A1541-&-/. OB>.P *%& .5*++&% A1541-&-/. ,1% 0I"AI /I&.*5& ". /%$&; C- &54"%"A*+ ./$)"&. /I& <=>> ". 1,/&- ,1$-) /1 6& .&N&%*+ 1%)&%. 1, 5*#-"/$)& +*%#&% /I*-*-@ 1, /I& B>. O.&& Q%1)&% "& *-3 O7999PP;HI& <=>> A1-."./. 1, * )%*$& 4&5'$)-. /'$$"/&"0 /'12'$"$& O<3>>P8 * )%*$& '6&7/'12'$"$& O<FGHP8* )%*$& %$7/'12'$"$& O<CDP *-) &"$05%-4 O.&& !"#$%& 'P; HI& <3>> A154%".&. *++ -1)&. /I*/ A*- %&*AI &N&%@1/I&% -1)& "- /I& <3>> /I%1$#I * )"%&A/&) 4*/I; R -1)& ". "- /I& <FGH ", "/ I*. * 4*/I ,%15 /I& <3>>6$/ -1/ /1 /I& <3>>; C- A1-/%*./8 * -1)& ". " - /I& <CD ", "/ I*. * 4*/I /1 /I& <3>> 6$/ -1/ ,%15 "/; R-1)& ". "- * /&-)%"+ ", "/ )1&. -1/ %&.")& 1- * )"%&A/&) 4*/I /1 1% ,%15 /I& <3>>;S9!%4/644%'$( C- /I& -&/01%2 1, 4*@5&-/. .&-/ 1N&% !&)0"%& *-*+@T&) 6@ 31%*5U2" "& *-3 O799:P8 /I& <3>>". /I& +*%#&./ A1541-&-/; F- *N&%*#&8 *+51./ %&' 1, /I& -1)&. "- /I*/ -&/01%2 6&+1-# /1 /I& <3>>; C-A1-/%*./8 /I& <3>> ". 5$AI .5*++&% ,1% /I& ,&)&%*+ ,$-). -&/01%2; C- 799:8 1-+@ (&' ) (' 1, /I& -1)&.6&+1-# /1 /I". A1541-&-/; Q@ ,*% /I& +*%#&./ A1541-&-/ ". /I& <CD; C- 799:8 )%' ) )' 1, /I& -1)&. 0&%&"- /I". A1541-&-/; HI& <FGH A1-/*"-&) (*' ) +' 1, *++ -1)&. 4&% )*@8 0I"+& /I&%& 0&%& (+' ) ,' 1,/I& -1)&. +1A*/&) "- /I& /&-)%"+.;SSV&.. /I*- -' ) (' 1, /I& -1)&. 0&%& "- /I& %&5*"-"-# )".A1--&A/&)A1541-&-/. O.&& H*6+& JP;S9HI& /&-)%"+. 5*@ *+.1 6& )"W&%&-/"*/&) "-/1 /I%&& .$6A1541-&-/.( * .&/ 1, -1)&. /I*/ *%& 1- * 4*/I &5*-*/"-# ,%15 <CD8 *.&/ 1 , - 1 )& . /I */ *%& 1 - * 4*/I +&*)"-# /1 < F G H8 *-) * .&/ 1, -1 ) &. /I*/ *%& 1- * 4*/I /I* / 6&#"-. "- < CD *-) & -). "- <F G H ;SS!!"# 1, -1 )&. 0&%& "- X,%15 E<CDY /&-)%"+.8 $!%# 1, -1 )&. 0&%& "- /I& X/1E<FG HY /&-)%"+. *-) "!&# 1, -1 )&. 0&%& "-X/$6 &.Y ,%15 < CD /1 <F GH ;S7Vertex = variable; edge = logical implication.6Implication graph~x0~x3~x1~x5x6x5~x6~x4~x2x2x4x1x3x0if x5 is true,then x0 is trueVertex = logical gate; edge = wire.7Combinational circuitVertex = synset; edge = hypernym relationship.8WordNet graphhttp://wordnet.princeton.edueventhappening
View Full Document