Networks in System ArchitectureWhy Study Networks?Every (Network) Model Is a Choice of Level of AbstractionNRC Report on “Network Science”Graphs and NetworksSingle Mode and MultimodeGraph/Network “Rules”Nodes Can BeArcs/links Can BeGraphs Can Be Classified As…A Classification of NetworksAdvantages of Graph RepresentationsDisadvantages or Shortcomings of Typical ModelsReal and “Not Real” NetworksGraph TheorySome Theoretical or Canonical Graph TypesExamples of various types of networks.The 2 best studied information networks; citation network and the World Wide WebAnother Well-Studied Network: The Karate Club“Traditional” Network TheoryExample NetworksMore Example Analyzable NetworksPossible AnalysesMatrix RepresentationBasic Graph Definitions and CalculationsBasic Facts About Undirected GraphsRewiringRewiring - 2More Definitions and CalculationsPlanar Graph ExampleMatlab RoutinesSimple TestAnotherLink Between Networks and SystemsAlexander’s Depiction of System DesignSimon and Alexander“New” Network TheoryDiameter and StructurePart of Western Power GridGlynn & Pelland’s Maps of Decisions and LocationsHierarchy of MetabolismClustering of Metabolic Reactions“Motifs” in NetworksShip Steam SystemCape Cod RoadwaysNetwork Analysis of Electric CircuitsPossible Data SetsTutorial BookResources, with search pathsMore ResourcesMoreProminent Network ResearchersBackupGraphs and MatricesLink Between Networks and Linear Algebra“Scale Free” and “Scaling”The Aura of Scale Free8/24/2006 © Daniel E. Whitney 1Networks.pptNetworks in System Architecture• Goals of this class:• Background on graph theory and network representations - more to come in the following weeks• Network applications to system representations and analyses• Quantitative evaluations possible•Examples8/24/2006 © Daniel E. Whitney 2Networks.pptWhy Study 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• A theory for engineering systems based on these methods is just getting started8/24/2006 © Daniel E. Whitney 3Networks.pptEvery (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 needed8/24/2006 © Daniel E. Whitney 4Networks.pptNRC Report on “Network Science”Researchers across diverse domains share an implicit understanding that a network is more than topology alone. It also entails connectivity, resource exchange, and localityof action.• Connectivity. A network has a well-defined connection topology in which each discrete entity (node) has a finite number of defined connections (links) to other nodes. In general, these links are dynamic. • Exchange. The connection topology exists in order to exchange one or more classes of resource among nodes. Indeed, a link between two nodes exists if and only if resources of significance to the network domain can be directly exchanged between them. • Locality. The exchanged resource is delivered, and its effects take place, only in local interactions (node to node, link to link). This locality of interaction entails autonomous agents actingon a locally available state.8/24/2006 © Daniel E. Whitney 5Networks.pptGraphs and Networks• A graph is a collection of nodes connected by arcs (directed, with arrows) or links (undirected, no arrows)– In graph theory, undirected links are called edges• A network is a graph8/24/2006 © Daniel E. Whitney 6Networks.pptSingle Mode and Multimode• Single mode network– Nodes are identical• Multimode– Nodes can be in different classes– People– Events attended by those people– Equivalent to two or more single mode networks• Common multimode is bipartiteFigures removed for copyright reasons. See Newman, M. E. J., and J. Park. "Why social networks are different from other types of networks." Phys Rev E 68, no. 036122 (2003).8/24/2006 © Daniel E. Whitney 7Networks.pptGraph/Network “Rules”• Links connect pairs of nodes• Links can be directed or undirected• Nodes can have any number of impinging links• Dual graphs can be formed– Arcs become nodes– Nodes become arcs8/24/2006 © Daniel E. Whitney 8Networks.pptNodes Can Be• Places•Things• Jobs, tasks, process steps• Calculations or calculation steps8/24/2006 © Daniel E. Whitney 9Networks.pptArcs/links Can Be• Physical paths, mechanical joints• Abstract or real relationships– Directed: A commands B, is the father of B, occurs before B…– Undirected: A lives near B, is on the same side as B…• Indications of flow of material or information• Annotated to represent capacity, direction, content• Carriers of single or multiple geometric dimensions8/24/2006 © Daniel E. Whitney 10Networks.pptGraphs Can Be Classified As…• Metric (arcs have real lengths, and node locations obey the triangle inequality)• Non-metric (the layout is purely logical)• Planar (can be drawn so that no arcs cross)• Connected or unconnected– Connected: a path exists between every pair of nodes• Simple: no self-loops, ≤ 1 link between nodes• Able/unable to support a looped path or a path that touches every node• These are not mutually exclusiveA Classification of NetworksFormal Tree-StructuredUnique Path to the T(No horizontal linksStrictly OrderedPure Layered StructNo layer-skippingHorizontal links allowPartially OrderedHierarchiesOrderedTop NodeRegularGeneral NetworksNon-HierarchicalUnorderedNo top nodeNetworksArcs, NodesArc joins exactly 2 nThis classification isa formal tree-structuredhierarchySimple8/24/2006 © Daniel E. Whitney 11Networks.ppt8/24/2006 © Daniel E. Whitney 12Networks.pptAdvantages of Graph Representations• Abstraction• Sharp focus on relationships • Ability to calculate many relevant properties of the modelled system, including many that accommodate huge graphs8/24/2006 © Daniel E. Whitney 13Networks.pptDisadvantages or Shortcomings of Typical Models• Multiple properties often require separate graphs• Nodes and arcs are usually treated as identical– Seeking abstraction– Not knowing enough about the system– Exceptions: arcs
View Full Document
Unlocking...