Networks in System Architecture • Network research history • Example complex systems represented as networks • Network models –Forming –Analyzing • Some fundamental questions Networks_Intro.ppt © Daniel E. Whitney 1/44Network Traditions and Emphases • Common foundation in graph theory (Euler) and desire to represent relationships • OR Optimization and Flow (1900s-1980s? Or now?) – Logistics, shortest paths, optimal allocation… – Ahuja, Magnanti, and Orlin • Social Network Theory (1970s-now?) – Focus on relationships – Abstract models, seeking system structural insights from metrics: cliques, clusters, power brokers, gate-keepers – Wasserman and Faust • “New” Network Science (1990s-now) – Abstract models, seeking system structural insights from metrics – Statistical approach – Barabasi, Watts, Newman Networks_Intro.ppt © Daniel E. Whitney 2/44“New” Network Science • Primary researchers are statistical physicists and mathematicians plus some social scientists and ecologists • Differ from SNT and OR traditions – Averaging metrics over ensembles of graphs – metrics view – Modeling of network growth – Comparison to physical systems like critical point phenomena and percolation – Network vulnerability – New metrics – Erdös-Rényi random graphs as the normative basis – Interest in really big networks, so big that you can’t display them, so only a metrics and statistical approach can be used • Field seems immature, with some lack of consistent methods and standards of proof, but very dynamic, big mix of disciplines and methods, big ambitions… Networks_Intro.ppt © Daniel E. Whitney 3/44Why Study Networks? • Many systems are networks • Networks capture relationships • Networks have structure (possibly random) • Various metrics exist that capture various aspects of this structure • In some cases the structure or the metrics can be related to important properties of the system or its behavior Networks_Intro.ppt © Daniel E. Whitney 4/44Modeling Questions Node • What is a node? Link • What is a link? • What are the important relationships that a model should try to capture? • What are the data that would be desired to build a useful model? • How much of the data can you really get? • What are fundamental limitations of the model? Networks_Intro.ppt © Daniel E. Whitney 5/44Some Theoretical or Canonical Graph Types •Planar • Random • Grid structured •Trees • Hub and spokes • “Scale free” • Possessing Hamilton or Euler circuit – Hamilton: touching every node once – Euler: touching every arc once Networks_Intro.ppt © Daniel E. Whitney 6/44Example Graphs (Systems) • Road map • Electric circuit or pipe system • Structure of bridge or building, with load paths • Organizational chart or social network • Markov chain • Control circuit feedback loop • Phone system • Chemical reaction • Sequential event plan Networks_Intro.ppt © Daniel E. Whitney 7/44More Example Analyzable Graphs • Manufacturing process • Assembly sequence • Schedule •Family tree • Ecological food chain • Taxonomy of living things, rocks, and other natural hierarchies • Naval battle, military campaign Networks_Intro.ppt © Daniel E. Whitney 8/44Planar Graph Example V = number of nodes E = number of edges f = number of facets f E ≤ 3V − 6 ∴ f = 2V − 4max Meshness Ratio M = f / fmax = E − V + 2 (or 1 if the "outside" facet is ignored) 0 ≤ M ≤ 1 Trails made by ants in planar sand piles have average nodal degree <k> = 2.2 and M ~ 0.1 Note: for connected planar graphs: 6V − 12< k > = ⎯ ⎯⎯→6max V →∞V < k > ⎯⎯⎯→ 4 M + 2 2V − 2 V →∞ < k >min = ⎯ ⎯⎯→2VV →∞ “Efficiency and Robustness in Ant Networks of Galleries,” J. Buhl, J. Gautrais1, R.V. Sol´e, P. Kuntz, S. Valverde2, J.L. Deneubourg, and G. Theraulaz, Eur. Phys. J. B 42, 123–129 (2004) Networks_Intro.ppt © Daniel E. Whitney 9/44 Metro systems: <k> = 3 - 3.5 mr = ~ 0.25Network Analysis of Electric Circuits This article does not use the word planar ŅTopology of technology graphs: Small world patterns in electronic circuits,Ó Ramon Ferrer i Cancho, Christiaan Janssen, and Ricard V. Sole, PHYSICAL REVIEW E, VOLUME 64 046119 Š 1 thru - 5 Networks_Intro.ppt © Daniel E. Whitney 10/44Network Version of London Tube Map Circle Line Node: terminal Or you can change trains Or the line branches Networks_Intro.ppt © Daniel E. Whitney 11/44A Circle Line Creates Shortcuts for Some TripsR N= 6 α = 1 α = 2 ρ/r = απ/N r ρ Networks_Intro.ppt © Daniel E. Whitney 12/44Growth Model of Tokyo Area Rail System by Slime Mold Image of slime mold growth and diagram of Tokyo area rail system removed due to copyright restrictions. Science 22 January 2010: Vol. 327. no. 5964, pp. 439 - 442 DOI: 10.1126/science.1177894 Rules for Biologically Inspired Adaptive Network Design Atsushi Tero,1,2 Seiji Takagi,1 Tetsu Saigusa,3 Kentaro Ito,1 Dan P. Bebber,4 Mark D. Fricker, 4 Kenji Yumiki,5 Ryo Kobayashi,5,6 Toshiyuki Nakagaki1,6,* Networks_Intro.ppt © Daniel E. Whitney 13/44Every (Network) Model Is a Choice of Level of Abstraction • “High” abstraction – Summarize, generalize, compare – Don’t need domain knowledge • “Low” abstraction – Valid detail – Explainable differences – Need domain knowledge • Models and analyses at many levels are needed Networks_Intro.ppt © Daniel E. Whitney 14/44Graphs and Networks • A graph is a collection of nodes connected by arcs (directed, with arrows) or edges (undirected, no arrows) generically called links • A network is a graph Networks_Intro.ppt © Daniel E. Whitney 15/44Graph/Network “Rules” • Links connect pairs of nodes • Links can be directed or undirected – Undirected called edges in graph theory – Directed called arcs • Nodes can have any number of impinging links in principle, although there may be various constraints that depend on the domain • Dual graphs can be formed – Links become nodes – Nodes become links Networks_Intro.ppt © Daniel E. Whitney 16/44Nodes Can Be • Places •Things • People • Jobs, tasks, process steps • Calculations or calculation steps Networks_Intro.ppt © Daniel E. Whitney 17/44Links Can Be • Physical paths, mechanical joints • Abstract or real relationships –
View Full Document
Unlocking...