matrix representation of graph ppt

Matrix Representations of Graphs

Apr 05, 2019

460 likes | 616 Views

Matrix Representations of Graphs. Benjamin Martin, Christopher Mueller, Joseph Cottam, and Andrew Lumsdaine Open Systems Lab/Indiana University. Introduction. Introduction to Visual Similarity Matrices Interpreting Visual Similarity Matrices

Share Presentation

• different methods
• first search algorithms
• evaluation stability
• vertex properties
• minimal structure
• bfs case study

Presentation Transcript

Matrix Representations of Graphs Benjamin Martin, Christopher Mueller, Joseph Cottam, and Andrew Lumsdaine Open Systems Lab/Indiana University

Introduction • Introduction to Visual Similarity Matrices • Interpreting Visual Similarity Matrices • Christopher Mueller, Benjamin Martin, and Andrew Lumsdaine. Interpreting Large Visual Similarity Matrices. In Asia-Pacific Symposium on Visualization, February 2007 • A Comparison of Ordering Algorithms • Christopher Mueller, Benjamin Martin, and Andrew Lumsdaine. A Comparison of Vertex Ordering Algorithms for Large Graph Visualization. In Asia-Pacific Symposium on Visualization, February 2007 • BFS Case Study

Visual Similarity Matrices Essentially, draw the adjacency matrix • Axes are labeled with the vertex names • Matrix dots represent graph edges

Visual Similarity Matrices Advantages: • Capable of representing much larger graphs • No risk of occlusion or edge crossings • Good for large and dense graphs, for most tasks See M. Ghoniem, J.-D. Fekete, and P. Castagliola. “On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis.” In Information Visualization, volume 4, pages 114–135, 2005.

Visual Similarity Matrices But VSMs must be ordered Expert Ordering NCI AIDs Screen Data Random Ordering So how do we do that?

Questions • How do we order a VSM? • How do we decide between different methods? • How do we interpret the results?

Interpreting VSMs Some features of VSMs are dependent on the matrix ordering, some are not

Interpreting VSMs Straight horizontal or vertical lines show “star” connectivity patterns in a graph. Noncontiguous lines carry the same information as contiguous lines Diagonal lines carry information if they are more than one pixel wide. May have to look at information elsewhere in the matrix… New edges

Interpreting VSMs Wedges appear on the diagonal and represent cliques Off-diagonal blocks are bi-partite sub-graphs. Blank rows or columns for a vertex remove the vertex from the component. Blocks and wedges can be joined across rows and columns: • - A is a clique (mirrored on the diagonal) • - B, C, D are bi-partite sub-graphs • - A + B, A + C are cliques • A + B + C + D is a clique • A and D are independent w/o additional • supporting structures

Interpreting VSMs Some ordering algorithms may produce characteristic patterns in the VSM Envelope footprints are indicative of breadth-first search algorithms. Horizon footprints suggest depth-first algorithms. Galaxy footprints are caused by algorithms that don’t follow direct paths through the graph.

Ordering • Algorithms • Breadth first search • Depth first search • Degree ordering • Reverse Cuthill-McKee (RCM) • King’s algorithm • Sloan’s algorithm • Separator tree • Spectral Ordering

Data • Synthetic Graphs (100, 500, 1000 vertices) • Erdős-Renyi • Small World • Power-law • K-partite • “K-linear-partite” • Real • COGSimilar - 1770 vertices, 290k edges • COGDissimilar - 2030 vertices, 158k edges • NCIca - 436 vertices, 18.6k edges • NCIall - 42,750 vertices, 3.29M edges

Methods: VSM Preparation … (1) (2) (3) (4) Create or load each graph Create two initial vertex orderings in memory: original and random Apply each algorithm to each initial ordering Generate hi-res (1000x1000) and lo-res (100x100) version of each VSM

Coarse/fine structure Coarse structure Minimal structure No structure Stable: similar structure Structure: dissimilar structure Ordered: only original has structure No structure Methods: Evaluation Stability: Compare original and random pairs with new ordering Interpretability: Evaluate quality of structure in each image

Results: Stability • Synthetic graphs tended to be stable for all algorithms • Real graphs • “Stable” for degree, partitioning, and spectral algorithms • “Structured” for search-based algorithms Stability is dependent on the graph and algorithm

Results: Interpretability Graphs with regular or dense connection patterns exhibited coarse and fine structure Structural artifacts from each algorithm were evident across all graph types

Results: BFS • “Envelope” footprint • Retains some internal structure from original ordering • Imparts structure on ER graphs

Results: DFS • “Horizon” footprints • Strong diagonal • Some internal structure added to visualization

Results: Degree • Visually reveals degree distribution • Poorest overall results

Results: RCM and King • Both impart additional structure within the envelope created by the BFS

Results: Separator Tree • Characterized by a “fat” diagonal • Nearly reproduces ordering for small world graph

Results: Sloan • Best overall • Similar results, regardless of initial ordering, for all graph types

Results: Spectral • “Galaxy” footprint • Performed well on structured graphs and fully resolved KL5 graphs

Ordering Conclusions • If structure is present in the data, all algorithms provide clues to it • Amount of connectedness has the largest positive impact on ordering quality • Randomness in data has the largest negative impact on ordering quality • Algorithms that looked at global and local properties performed best

Implementation Issues Interactivity is essential for exploring large graphs. Alternate orderings allow for different views and interpretations. Linked views, especially for vertex properties, help explore structural features. Edges (dots) can be colored by weight or category. Anti-aliasing is essential for large, sparse graphs: The graph on the right is easily interpreted as a dense graph with little structure. The image on the left provides a more accurate rendering of the graph.

Some Lessons • VSMs are compelling tools for exploring large graphs • Care must be taken to ensure proper interpretations are made • Interactive tools that provide multiple views of the graph are useful for exploring large VSMs

BFS Case Study BFS shows remarkable consistency over several graph types, especially SWGs Can we better characterize its behavior? Specifically, can we quantify some of the things we’re seeing?

BFS Case Study

Visual Parameters • Bandwidth and average envelope width • Envelope jump • Envelope terminal • Number of envelope gaps • Average gap width

Graph Measurements • Diameter • Characteristic path length • Global efficiency • Clustering coefficient • Model parameters n, k, p

Graph Measurements

BFS Case Study We begin by considering fixed n and k, and looking at diameter and average envelope width.

Average Envelope Width and Diameter

Global Efficiency

Generalizing What about other n and k?

Generalizing

Summary • Average envelope width is an effective and simple predictor of global efficiency for Watts-Strogatz graphs • Which indirectly gives us the diameter • And hopefully this works with other graph types

Possible directions • Look at more diverse data • Look at other orderings, especially spectral

Acknowledgements Funding: Lily Endowment National Science Foundation grant EIA-0202048. Software and Algorithms: Doug Gregor (Boost Graph Library) Jeremiah Willcock (Separator Tree) Data: Sun Kim (PLATCOM) David Wild (NCI)

• More by User

Representations

Representations. One of the major distinctions between ordinary software and AI is the need to represent domain knowledge (or other forms of worldly knowledge) this knowledge must be represented in some form

669 views • 30 slides

Exploring Social Networks with Matrix-Based Representations

Exploring Social Networks with Matrix-Based Representations. Nathalie Henry* & Jean-Daniel Fekete IN|SITU / AVIZ Lab. INRIA / Laboratoire de Recherche en Informatique *Université de Sydney [email protected] , [email protected]. The problem.

546 views • 28 slides

Lecture 2 Sparse matrix data structures, graphs , manipulation

4 th Gene Golub SIAM Summer School, 7/22 – 8/7, 2013, Shanghai. Lecture 2 Sparse matrix data structures, graphs , manipulation. Xiaoye Sherry Li Lawrence Berkeley National Laboratory , USA xsli@ lbl.gov crd-legacy.lbl.gov /~ xiaoye /G2S3 /. Lecture outline.

521 views • 37 slides

GRAPHICAL REPRESENTATIONS OF A DATA MATRIX

GRAPHICAL REPRESENTATIONS OF A DATA MATRIX. SYSTEM CHARCTERISATION. SYSTEM. Measure. Numbers. CHARACTERISATION. Sample. Instrument + Computer. UV,IR,NMR, MS,GC,GC-MS. Instrumental Profiles. Data matrix. ..................... .................... . . Numbers. Measure.

417 views • 27 slides

Representations of age

Representations of age. How are the following represented in the media? Teenagers Old people Middle aged people (45 – 55). What are the representations?. How are they constructed?. How has Catherine Tate represented ‘Nan’? Is she stereotypical? Why? Why not? Look at her iconography.

473 views • 31 slides

Representations. Representation. Studying representations is one of the important elements of the Stage 2/3 course Studying representations helps you understand texts on a deeper level

239 views • 7 slides

Representations of Integers

Representations of Integers. How can we construct the base b expansion of an integer n? First, divide n by b to obtain a quotient q 0 and remainder a 0 , that is, n = bq 0 + a 0 , where 0  a 0 < b. The remainder a 0 is the rightmost digit in the base b expansion of n.

450 views • 31 slides

EQ2,3,4: How can I interpret graphs and tabular representations of data?

EQ2,3,4: How can I interpret graphs and tabular representations of data?. Notes & Vocabulary Classwork: p.759, #3,4 Workbook – p.247-8 Mid-Chapter Quiz - GRADED. 13.05 13.11. 13.18. 13.19. Measures of Central Tendency.

217 views • 6 slides

Representations of speech

Representations of speech. To explore discourse structure within The Lovely Bones. Discourse Structure . This is the scariest of all the frameworks we use, but basically all we need to ask ourselves is: ‘How does the text fit together? Why has the writer chosen to put it together in this way?’.

206 views • 10 slides

Compact Representations of Separable Graphs

Compact Representations of Separable Graphs. From a paper of the same title submitted to SODA by: Dan Blandford and Guy Blelloch and Ian Kash. Standard Graph Representations. Standard Adjacency List - |V| + 2|E| words = O(|E|lg|V|) bits - |V| + |E| words if stored as an array

311 views • 21 slides

Geometric Representations of Graphs

Geometric Representations of Graphs. A survey of recent results and problems Jan Kratochvíl, Prague. Outline of the Talk. Intersection Graphs Recognition of the Classes Sizes of Representations Optimization Problems Interval Filament Graphs Representations of Planar Graphs.

1.12k views • 95 slides

Exploring social networks with Matrix-based representations

Exploring social networks with Matrix-based representations. Nathalie Henry. Co-supervisors: Jean-Daniel Fekete & Peter Eades. Background. Peter Eades, Univ. of Sydney. Sociologists from EHESS, Historians from the French Archives, Analysts from EDF and France telecom.

537 views • 46 slides

Representations. The Chav. The Mother. The Father. Women. Teenagers. Celebrity Image. Geek.

171 views • 8 slides

Graphs and Matrix Storage Structures

Graphs and Matrix Storage Structures. EEE 574 Dr. Dan Tylavsky. In order to perform calculations on electric power networks we’ll need to have a way of representing them. The mathematical equivalent of a network is a graph. Some definitions:

417 views • 25 slides

Matrix Representations

Matrix Representations. Lesson 6.1.

303 views • 20 slides

Graphs: Adjacency Matrix

Graphs: Adjacency Matrix. Example:. 1. a. d. 2. 4. b. c. 3. Breadth-First Search. “ Explore” a graph, turning it into a tree One vertex at a time Expand frontier of explored vertices across the breadth of the frontier Builds a tree over the graph

717 views • 16 slides

Matrix Representations of Knot and Link Groups Jess May 2006

Matrix Representations of Knot and Link Groups Jess May 2006. My Theorem Theorem : The nonabelian representations of a link group, ρ (K) into G, correspond to the roots of the multivariable Alexander polynomial, Δ (t i ).

86 views • 1 slides

216 views • 20 slides

Vocabulary and Representations of Graphs

Vocabulary and Representations of Graphs. NC Standard Course of Study. Competency Goal 1: The learner will use matrices and graphs to model relationships and solve problems. Objective 1.02 : Use graph theory to model relationships and solve problems. Graphs.

336 views • 33 slides

Explorers need maps: Abstraction, representations and graphs

Explorers need maps: Abstraction, representations and graphs. Paul Curzon Queen Mary University of London. With support from Google, D of E, the Mayor of London and CHI+MED. www.teachinglondoncomputing.org Twitter: @TeachingLDNComp. Aims. Give you deeper understanding of core topics

338 views • 32 slides

Computing NodeTrix Representations of Clustered Graphs

Computing NodeTrix Representations of Clustered Graphs. Roma Tre University. Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. NodeTrix Hybrid Representations. NodeTrix combines node-link and matrix-based representations [Henry, Fekete, McGuffin, IEEE TVCG, 2007].

250 views • 24 slides

Lecture 5.2: Special Graphs and Matrix Representation *

Lecture 5.2: Special Graphs and Matrix Representation *. CS 250, Discrete Structures, Fall 2011 Nitesh Saxena * Adopted from previous lectures by Zeph Grunschlag. Course Admin – Homework 4. Due tomorrow at 11am Do not forget the bonus problem Please submit on time.

440 views • 43 slides

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

12.1: Representing a Graph by a Matrix

• Last updated
• Save as PDF
• Page ID 8485

• Carleton University via Athabasca University Press

An adjacency matrix is a way of representing an \(\mathtt{n}\) vertex graph \(G=(V,E)\) by an \(\mathtt{n}\times\mathtt{n}\) matrix, \(\mathtt{a}\), whose entries are boolean values.

The matrix entry \(\mathtt{a[i][j]}\) is defined as

\[\mathtt{a[i][j]}= \begin{cases} \mathtt{true} & \text{if } \mathtt{(i,j)}\in E \\ \mathtt{false} & \text{otherwise} \end{cases}\nonumber\]

The adjacency matrix for the graph in Figure 12.1 is shown in Figure \(\PageIndex{1}\).

In this representation, the operations \(\mathtt{addEdge(i,j)}\), \(\mathtt{removeEdge(i,j)}\), and \(\mathtt{hasEdge(i,j)}\) just involve setting or reading the matrix entry \(\mathtt{a[i][j]}\):

These operations clearly take constant time per operation.

Where the adjacency matrix performs poorly is with the \(\mathtt{outEdges(i)}\) and \(\mathtt{inEdges(i)}\) operations. To implement these, we must scan all \(\mathtt{n}\) entries in the corresponding row or column of \(\mathtt{a}\) and gather up all the indices, \(\mathtt{j}\), where \(\mathtt{a[i][j]}\), respectively \(\mathtt{a[j][i]}\), is true.

These operations clearly take \(O(\mathtt{n})\) time per operation.

Another drawback of the adjacency matrix representation is that it is large. It stores an \(\mathtt{n}\times \mathtt{n}\) boolean matrix, so it requires at least \(\mathtt{n}^2\) bits of memory. The implementation here uses a matrix of \(\mathtt{boolean}\) values so it actually uses on the order of \(\mathtt{n}^2\) bytes of memory. A more careful implementation, which packs \(\mathtt{w}\) boolean values into each word of memory, could reduce this space usage to \(O(\mathtt{n}^2/\mathtt{w})\) words of memory.

Theorem \(\PageIndex{1}\)

The AdjacencyMatrix data structure implements the Graph interface. An AdjacencyMatrix supports the operations

• \(\mathtt{addEdge(i,j)}\), \(\mathtt{removeEdge(i,j)}\), and \(\mathtt{hasEdge(i,j)}\) in constant time per operation; and
• \(\mathtt{inEdges(i)}\), and \(\mathtt{outEdges(i)}\) in \(O(\mathtt{n})\) time per operation.

The space used by an AdjacencyMatrix is \(O(\mathtt{n}^2)\).

Despite its high memory requirements and poor performance of the \(\mathtt{inEdges(i)}\) and \(\mathtt{outEdges(i)}\) operations, an AdjacencyMatrix can still be useful for some applications. In particular, when the graph \(G\) is dense , i.e., it has close to \(\mathtt{n}^2\) edges, then a memory usage of \(\mathtt{n}^2\) may be acceptable.

The AdjacencyMatrix data structure is also commonly used because algebraic operations on the matrix \(\mathtt{a}\) can be used to efficiently compute properties of the graph \(G\). This is a topic for a course on algorithms, but we point out one such property here: If we treat the entries of \(\mathtt{a}\) as integers (1 for \(\mathtt{true}\) and 0 for \(\mathtt{false}\)) and multiply \(\mathtt{a}\) by itself using matrix multiplication then we get the matrix \(\mathtt{a}^2\). Recall, from the definition of matrix multiplication, that

\[\mathtt{a^2[i][j]} = \sum_{k=0}^{\mathtt{n}-1} \mathtt{a[i][k]}\cdot \mathtt{a[k][j]} \enspace .\nonumber\]

Interpreting this sum in terms of the graph \(G\), this formula counts the number of vertices, \(\mathtt{k}\), such that \(G\) contains both edges \(\mathtt{(i,k)}\) and \(\mathtt{(k,j)}\). That is, it counts the number of paths from \(\mathtt{i}\) to \(\mathtt{j}\) (through intermediate vertices, \(\mathtt{k}\)) whose length is exactly two. This observation is the foundation of an algorithm that computes the shortest paths between all pairs of vertices in \(G\) using only \(O(\log \mathtt{n})\) matrix multiplications.

Graph Neural Networks

Lecture 3: Graph Convolutional Filters (9/19 – 9/22)

We begin our exploration of the techniques we will use to devise learning parametrization for graphs signals. In this lecture we study graph convolutional filters. Although we already defined graph convolutions in Lecture 1, this lecture takes a more comprehensive approach. We formally define graphs, graph signals and graph shift operators. We introduce the diffusion sequence which we build through recursive application of the shift operator. This sequence is the basis for an alternative definition of graph filters as linear combinations of the components of the diffusion sequence. This is a definition that is more operational than the definition of graph filters as polynomials on the shift. We close the lecture with the introduction of the graph Fourier transform and the frequency representation of graph filters.

• Access full lecture playlist.

Video 3.1 – Graphs

We define graphs and discuss different types: Directed and symmetric and weighted and unweighted. Just a review to set up notation. Watch it quickly as a refresher.

• Covers Slides 1-6 in the handout.

Video 3.2 – Graph Shift Operators

It is standard to represent graphs with adjacency and Laplacian matrices. In the context of graph signal processing, these matrix representations of a graph are called graph shift operators. The notational conventions used in graph shift operators are a little different from the standard conventions of graph theory. It is worth taking a look. We also define normalized adjacency and Laplacian matrices.

• Covers Slides 7-15 in the handout.

Video 3.3 – Graph Signals

Graph signals are the objects we process with graph convolutional filters and, in upcoming lectures, with graph neural networks. They are defined as vectors whose components are associated to nodes of the graph. When given a graph signal, we can multiply it with the graph shift operator. This gives rise to the diffusion sequence, which is instrumental in coming up with operational definitions of graph filters.

• Covers Slides 16-20 in the handout.

Video 3.4 – Graph Convolutional Filters

We revisit the definition of graph convolutional filters. As before, we will write them as polynomials on a matrix representation of the graph. But we will also write them as linear combinations of the components of the diffusion sequence. This gives an alternative view of graph filters which is better connected to their practical implementation and applicability. We also establish a connection to familiar shift register structures.

• Covers Slides 21-25 in the handout.

Video 3.5 – Time Convolutions and Graph Convolutions

We revisit the fact that convolutions in time can be recovered as particular cases of graph convolutions when using the adjacency matrix of a directed line graph as shift operator. We take it more slowly and show how the shift register we use for convolutions in time is modified towards the construction of a graph shift register.

• Covers Slides 26-30 in the handout.

Video 3.6 – Graph Fourier Transform

The analysis of graph signals is an important component of this course. The fundamental tool we use to analyze graph signals is the graph Fourier transform (GFT). The GFT is defined as a projection of the signal in the eigenvector space of the graph. An inverse transform is defined as well.

• Covers Slides 31-34 in the handout.

Video 3.7 – Graph Frequency Response

The graph Fourier transform is leveraged to represent graph filters in the graph frequency domain. It will turn out that in this domain graph filters admit a pointwise representation in which individual frequency components of the input are scaled to produce individual frequency components of the output. This is another fundamental property that graph filters share with time convolutional filters.

• Covers Slides 35-40 in the handout.

Matrix Charts

Dive into our extensive collection of 93 matrix chart templates , designed to elevate your PowerPoint and Google Slides presentations to new heights. Matrix charts are a versatile visualization tool, helping you display complex data in an easy-to-understand format. Ideal for showcasing relationships, comparisons, or the positioning of various elements, these types of charts are perfect for presentations related to business strategy, marketing, decision-making, and risk assessment.

Matrix charts come in many forms, such as the Adjacency Matrix, Ansoff Matrix, Basic Matrix Layouts, BCG Matrix, and SWOT Analysis. Each type caters to specific needs, ensuring your presentation clearly conveys your intended message.

Make a lasting impact with our stunning matrix chart templates and graphics. Take advantage of these free resources to create an engaging, well-structured presentation that effectively communicates your insights.

Infographic Quadrant Pie Chart

Google Slides , PPTX

TOWS Analysis for PowerPoint and Google Slides

SWOT Analysis Deck for PowerPoint and Google Slides

Fourfold Ribbon Rings for PowerPoint and Google Slides

Four-Direction Divergence Diagram for PowerPoint and Google Slides

Light Bulb SWOT for PowerPoint and Google Slides

Quatrefoil with Central Rhombus for PowerPoint and Google Slides

Halo Radial for PowerPoint and Google Slides

SWOT Analysis for PowerPoint and Google Slides

Diverging Curved Arrows Matrix for PowerPoint and Google Slides

Simple Flower Matrix for PowerPoint and Google Slides

Cross Matrix for PowerPoint and Google Slides

Search templates by categories, search templates by colors.

Love our templates? Show your support with a coffee!

Thank you for fueling our creativity.

Charts & Diagrams

Text & Tables

Graphics & Metaphors

Timelines & Planning

Best-Ofs & Tips

Terms and Conditions

Privacy Statement

Cookie Policy

Digital Millennium Copyright Act (DMCA) Policy

© Copyright 2024  Ofeex  | PRESENTATIONGO® is a registered trademark | All rights reserved.

To provide the best experiences, we and our partners use technologies like cookies to store and/or access device information. Consenting to these technologies will allow us and our partners to process personal data such as browsing behavior or unique IDs on this site and show (non-) personalized ads. Not consenting or withdrawing consent, may adversely affect certain features and functions.

Click below to consent to the above or make granular choices. Your choices will be applied to this site only. You can change your settings at any time, including withdrawing your consent, by using the toggles on the Cookie Policy, or by clicking on the manage consent button at the bottom of the screen.

Thank you for downloading this template!

Remember, you can use it for free but you have to attribute PresentationGO . For example, you can use the following text:

If you really like our free templates and want to thank/help us, you can:

Thank you for your support

• Preferences

Matrix Representations of Graphs - PowerPoint PPT Presentation

Matrix Representations of Graphs

Benjamin martin, christopher mueller, joseph cottam, and andrew lumsdaine ... a comparison of vertex ordering algorithms for large graph visualization. ... – powerpoint ppt presentation.

• Benjamin Martin, Christopher Mueller, Joseph Cottam, and Andrew Lumsdaine
• Open Systems Lab/Indiana University
• Introduction to Visual Similarity Matrices
• Interpreting Visual Similarity Matrices
• Christopher Mueller, Benjamin Martin, and Andrew Lumsdaine. Interpreting Large Visual Similarity Matrices. In Asia-Pacific Symposium on Visualization, February 2007
• A Comparison of Ordering Algorithms
• Christopher Mueller, Benjamin Martin, and Andrew Lumsdaine. A Comparison of Vertex Ordering Algorithms for Large Graph Visualization. In Asia-Pacific Symposium on Visualization, February 2007
• BFS Case Study
• Essentially, draw the adjacency matrix
• Axes are labeled with the vertex names
• Matrix dots represent graph edges
• Capable of representing much larger graphs
• No risk of occlusion or edge crossings
• Good for large and dense graphs, for most tasks
• See M. Ghoniem, J.-D. Fekete, and P. Castagliola. On the readability of graphs using node-link and matrix-based representations a controlled experiment and statistical analysis. In Information Visualization, volume 4, pages 114135, 2005.
• How do we order a VSM?
• How do we decide between different methods?
• How do we interpret the results?
• Some features of VSMs are dependent on the matrix ordering, some are not
• - A is a clique (mirrored on the diagonal)
• - B, C, D are bi-partite sub-graphs
• - A B, A C are cliques
• A B C D is a clique
• A and D are independent w/o additional
• supporting structures
• Breadth first search
• Depth first search
• Degree ordering
• Reverse Cuthill-McKee (RCM)
• Kings algorithm
• Sloans algorithm
• Separator tree
• Spectral Ordering
• Synthetic Graphs (100, 500, 1000 vertices)
• Erdos-Renyi
• Small World
• K-linear-partite
• COGSimilar - 1770 vertices, 290k edges
• COGDissimilar - 2030 vertices, 158k edges
• NCIca - 436 vertices, 18.6k edges
• NCIall - 42,750 vertices, 3.29M edges
• Create or load each graph
• Create two initial vertex orderings in memory original and random
• Apply each algorithm to each initial ordering
• Generate hi-res (1000x1000) and lo-res (100x100) version of each VSM
• Stable similar structure
• Structure dissimilar structure
• Ordered only original has structure
• No structure
• Coarse/fine structure
• Coarse structure
• Minimal structure
• Synthetic graphs tended to be stable for all algorithms
• Real graphs
• Stable for degree, partitioning, and spectral algorithms
• Structured for search-based algorithms
• Envelope footprint
• Retains some internal structure from original ordering
• Imparts structure on ER graphs
• Horizon footprints
• Strong diagonal
• Some internal structure added to visualization
• Visually reveals degree distribution
• Poorest overall results
• Both impart additional structure within the envelope created by the BFS
• Characterized by a fat diagonal
• Nearly reproduces ordering for small world graph
• Best overall
• Similar results, regardless of initial ordering, for all graph types
• Galaxy footprint
• Performed well on structured graphs and fully resolved KL5 graphs
• If structure is present in the data, all algorithms provide clues to it
• Amount of connectedness has the largest positive impact on ordering quality
• Randomness in data has the largest negative impact on ordering quality
• Algorithms that looked at global and local properties performed best
• VSMs are compelling tools for exploring large graphs
• Care must be taken to ensure proper interpretations are made
• Interactive tools that provide multiple views of the graph are useful for exploring large VSMs
• Bandwidth and average envelope width
• Envelope jump
• Envelope terminal
• Number of envelope gaps
• Average gap width
• Characteristic path length
• Global efficiency
• Clustering coefficient
• Model parameters n, k, p
• We begin by considering fixed n and k,
• and looking at diameter and average envelope width.
• What about other n and k?
• Average envelope width is an effective and simple predictor of global efficiency for Watts-Strogatz graphs
• Which indirectly gives us the diameter
• And hopefully this works with other graph types
• Look at more diverse data
• Look at other orderings, especially spectral

PowerShow.com is a leading presentation sharing website. It has millions of presentations already uploaded and available with 1,000s more being uploaded by its users every day. Whatever your area of interest, here you’ll be able to find and view presentations you’ll love and possibly download. And, best of all, it is completely free and easy to use.

You might even have a presentation you’d like to share with others. If so, just upload it to PowerShow.com. We’ll convert it to an HTML5 slideshow that includes all the media types you’ve already added: audio, video, music, pictures, animations and transition effects. Then you can share it with your target audience as well as PowerShow.com’s millions of monthly visitors. And, again, it’s all free.

About the Developers

PowerShow.com is brought to you by  CrystalGraphics , the award-winning developer and market-leading publisher of rich-media enhancement products for presentations. Our product offerings include millions of PowerPoint templates, diagrams, animated 3D characters and more.

• School Guide
• Mathematics
• Number System and Arithmetic
• Trigonometry
• Probability
• Mensuration
• Maths Formulas
• Class 8 Maths Notes
• Class 9 Maths Notes
• Class 10 Maths Notes
• Class 11 Maths Notes
• Class 12 Maths Notes
• Engineering Mathematics Tutorials

Matrix and Determinants

• Different Operations on Matrices

Representation of Relation in Graphs and Matrices

• Determinant of a Matrix with Solved Examples
• Properties of Determinants
• Row Echelon Form
• Eigenvalues
• System of Linear Equations
• Matrix Diagonalization
• L U Decomposition
• Finding Inverse of a Square Matrix using Cayley Hamilton Theorem in MATLAB

Sequence and Series

• Binomial Theorem
• Sequences and Series
• Finding nth term of any Polynomial Sequence
• Mathematics | Sequence, Series and Summations
• Indeterminate Forms
• Mathematics | Limits, Continuity and Differentiability
• Cauchy's Mean Value Theorem
• Lagrange's Mean Value Theorem
• Rolle's Mean Value Theorem
• Taylor Series
• Maclaurin series
• Euler's Formula
• Chain Rule Derivative - Theorem, Proof, Examples
• Inverse functions and composition of functions
• Definite Integral
• Mathematics | Indefinite Integrals
• Application of Derivative - Maxima and Minima | Mathematics
• Summation Formula

Statistics and Numerical Methods

• Mean, Variance and Standard Deviation
• Mathematics - Law of Total Probability

Probability Distribution

• Bayes' Theorem
• Conditional Probability
• Mathematics | Probability Distributions Set 1 (Uniform Distribution)
• Mathematics | Probability Distributions Set 2 (Exponential Distribution)
• Mathematics | Probability Distributions Set 3 (Normal Distribution)
• Mathematics | Probability Distributions Set 4 (Binomial Distribution)
• Mathematics | Probability Distributions Set 5 (Poisson Distribution)
• Mathematics | Covariance and Correlation

Engineering Math Practice Problems

• Mathematics | Problems On Permutations | Set 1
• Problem on permutations and combinations | Set 2
• Mathematics | Graph theory practice questions
• Last Minute Notes - Engineering Mathematics

Previously, we have already discussed Relations and their basic types.   Combining Relation:   Suppose R is a relation from set A to B and S is a relation from set B to C, the combination of both the relations is the relation which consists of ordered pairs (a,c) where a ? A and c ? C and there exist an element b ? B for which (a,b) ? R and (b,c) ? S. This is represented as RoS.  Inverse Relation:   A relation R is defined as (a,b) ? R from set A to set B, then the inverse relation is defined as (b,a) ? R from set B to set A. Inverse Relation is represented as R -1 R -1 = {(b,a) | (a,b) ? R}.  Complementary Relation:   Let R be a relation from set A to B, then the complementary Relation is defined as- {(a,b) } where (a,b) is not ? R.  Representation of Relations:   Relations can be represented as- Matrices and Directed graphs.  Relation as Matrices:   A relation R is defined as from set A to set B, then the matrix representation of relation is M R = [m ij ] where  m ij = { 1, if (a,b) ? R   

0, if (a,b) does not ? R }  Properties:    

• A relation R is irreflexive if the matrix diagonal elements are 0.

• A relation R is antisymmetric if either m ij = 0 or m ji =0 when i?j.
• A relation follows join property i.e. the join of matrix M1 and M2 is M1 V M2 which is represented as R1 U R2 in terms of relation.
• A relation follows meet property i.r. the meet of matrix M1 and M2 is M1 ^ M2 which is represented as R1 ? R2 in terms of relation.

Relations as Directed graphs:   A directed graph consists of nodes or vertices connected by directed edges or arcs. Let R is relation from set A to set B defined as (a,b) ? R, then in directed graph-it is represented as edge(an arrow from a to b) between (a,b).  Properties:    

• A relation R is reflexive if there is loop at every node of directed graph.
• A relation R is irreflexive if there is no loop at any node of directed graphs.
• A relation R is symmetric if for every edge between distinct nodes, an edge is always present in opposite direction.
• A relation R is asymmetric if there are never two edges in opposite direction between distinct nodes.
• A relation R is transitive if there is an edge from a to b and b to c, then there is always an edge from a to c.

Example:   The directed graph of relation R = {(a,a),(a,b),(b,b),(b,c),(c,c),(c,b),(c,a)} is represented as :   

Since, there is loop at every node, it is reflexive but it is neither symmetric nor antisymmetric as there is an edge from a to b but no opposite edge from b to a and also directed edge from b to c in both directions. R is not transitive as there is an edge from a to b and b to c but no edge from a to c.      Related Articles:   Relations and their types    

Please Login to comment...

Similar reads.

• Engineering Mathematics
• School Learning

Improve your Coding Skills with Practice

What kind of Experience do you want to share?