Explore
For Enterprise
Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Notas
Certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

3.1.2. Embedding Planar Graphs

Loading...

Visualização de Dados

Universidade de Illinois em Urbana-ChampaignUniversidade de Illinois em Urbana-Champaign

4.5 (788 classificações) | 62K alunos inscritos

Curso 1 de 6 no Mineração de dadosData Mining Programa de cursos integrados

Learn the general concepts of data mining along with basic methodologies and applications. Then dive into one subfield in data mining: pattern discovery. Learn in-depth concepts, methods, and applications of pattern discovery in data mining. We will also introduce methods for pattern-based classification and some interesting applications of pattern discovery. This course provides you the opportunity to learn skills and content to practice and engage in scalable pattern discovery methods on massive transactional data, discuss pattern evaluation measures, and study methods for mining diverse kinds of patterns, sequential patterns, and sub-graph patterns.

Visualizar o programa do curso

Habilidades que você aprenderá

Data Visualization Software, Tableau Software, Data Virtualization, Data Visualization (DataViz)

Avaliações

4.5 (788 classificações)

5 stars
505 ratings
4 stars
195 ratings
3 stars
52 ratings
2 stars
24 ratings
1 star
12 ratings

SM

Dec 15, 2016

One of the excellent courses I have ever studied. Professor style of teaching is very soft and simple, point to point and very clear. I have given 100 out 100 marks.

CY

Nov 27, 2017

Really like this course which leads me to Tableau. After the course, I take about 8 hours to learn Tableau and I think my ability of data visualization ballooned.

Na lição

Week 3: Visualization of Non-Numerical Data

In this week's module, you will learn how to visualize graphs that depict relationships between data items. You'll also plot data using coordinates that are not specifically provided by the data set.

3.1.1. Graphs and Networks8:16

3.1.2. Embedding Planar Graphs11:37

3.1.3. Graph Visualization13:50

3.1.4. Tree Maps9:21

Ministrado por

John C. Hart
Professor of Computer Science

Transcrição

[MUSIC]

So when we visualize data organized as a graph,

we'll likely want to lay it out in a plane.

There's a kind of graph that enables that called a planar graph.

So as we saw before we're going to represent data items as nodes and

edges between nodes will represent relationships between those data items.

In some cases we'll have a graph, a planar graph for example.

A planar graph can be drawn such that the edges connecting the nodes don't cross.

That's called a planar embedding.

The same planar graph,

in this case you've got the same foreign nodes connected by the same five edges.

In this non planar embedding the edges cross.

And so, the same graph, they're both planar graphs.

What we'd like to do is be able to find the embedding,

the way to lay out the nodes so that the edges don't cross, so

it'll be clearer to the observer, the relationship between the nodes.

So we can do this.

We can do this for very large graphs.

For example, here's a triangle mesh representing a geometric object.

It's a triangle mesh, so the vertices are nodes and

the edges of the triangles form the edges between the nodes.

This graph, this large graph of 50,000 nodes is not a planar graph,

but if I make cuts in it, if I separate the faces and duplicate edges,

I can turn it into a planar graph just by making these cuts along the black lines.

And as a planar graph, I can then find a way of embedding it into the plane so

that the edges don't cross.

There's so many nodes and so many edges in this this graph and

it's hard to see all of the edges, so trust me that they don't cross.

Hopefully you'll be working with fewer nodes and edges so

that your layouts will be a little more clear than this.

So there's a way we can find these embeddings automatically, and

it's called Tutte's Method, and it starts by picking some of your nodes and

defining where they should be in the layout.

So in this case, I'm going to use eight nodes, 12 edges that make a cube,

and I'm going to take these first four nodes,

and I'm going to find positions for them in for example an SVG Canvass.

I'm going to position node 1 at (0,0), node 2 at (1,0),

node 3 at (0,1), and node 4 at node (1,1).

And then I'm going to try to figure out where do I want to position nodes 5, 6, 7,

and 8, in order to make a plainer embedding of this graph.

This graph is shown in a non planar embedding,

because we've got edge crossings.

We want to find out how to make a planar embedding of it.

So in order to do this automatically for any graph,

we're going to need to solve a linear system.

So we'll create a matrix.

In fact, an adjacency matrix,

a special kind of adjacency matrix called a Laplacian matrix.

So it's an adjacency matrix which means,

I'm going to take one node to another node in case of node 1 is connected to node 2,

so in row one, column two, I'm going to have a non zero entry.

In this case, the non zero entry is going to be 1 over the degree.

The node one has degree three,

it has three edges extending from it, so I'll put a one-third there.

And so node 1 is connected to nodes 2, 3, and 5,

and so I'll put one-third in columns two, three, and

five, and node one isn't connected to the other nodes.

So in those columns including node one, in those columns I'll put a zero.

The nice thing about the Laplacian form of an adjacency

matrix is the for node 1 I'm connected to three items.

My degree is three.

The value I'm putting in is one over the degree.

So if I add all of the elements up for row one I get one.

So no we're going to create a special matrix from that Laplacian adjacency

matrix.

We'll just call this matrix A.

First thing I'm going to do is I'm going to take that Laplace matrix, and

I'm going to zero out all of the rows for the nodes I've already assigned.

So I've already assigned Node 1, 2, 3, and 4 a position.

So I'll just zero those out in my adjacency matrix,

subtract the whole thing from the identity matrix.

The identity matrix just has ones down the diagonal and zeros everyplace else.

That will give me this matrix A that I'm going to solve

in order to find the placements for nodes 5, 6, 7, and 8.

So I need to set up a linear system, and so

we'll set up a linear system for the x coordinates of our nodes, and

then we'll set up a separate linear system for the y coordinates.

So the linear system we use for the x coordinates looks like this.

It's my matrix A, and then I've got times x,

a column vector that's just the x coordinates of my nodes, and

then finally I've got the answer, what the x coordinates actually should be in

the case of the first four nodes and then zeros for the nodes I want to solve.

So this is saying that one times x one, the x coordinate of node one,

one time x one and zero times everything else equals zero.

Because that what I've assigned.

So here I've got node 0, node 1, nodes 2 and node 3,

these are the x coordinates of node 1, 2, 3, and 4.

And so here I've got one, this second row.

1 times x2 is equal to 1, and the x coordinate of a sine for node two is one.

So that's what I put in these first entries

of this bx column vector, and the remaining entries are just zero.

The nice thing here is that if we look at row five,

row five says that the x coordinate of node 5, x5,

one times x5 minus one-third times x1,

minus one-third times x6,

minus one-third times x7, is going to be equal to zero.

That's basically setting up a linear equation so

that wherever I position nodes 6 and 7, they're going to impact node 5.

Once we do that for rows five, six, seven, and eight corresponding to nodes 5,

6, 7, and 8, and when we solve this system we'll have positions for

nodes 5, 6, 7, and 8 that solve that relationship.

Do the same thing for the y coordinates.

So now my by column vector is equal to the y coordinates for nodes 1, 2,

3 and 4 that I've placed, and then add zeroes for everything else.

Node 1 has zero for the y coordinate.

Node 2 has zero for the y coordinate.

Node 3 has one for the y coordinate, and node 4 has one for the y coordinate,

and this is basically saying that y1 = 0, y2 = 0, y3 = 1, y4 = 1.

But it's saying that the y coordinate for

node 5 is equal to whatever the y coordinate is for node 5, minus one-third,

times the y coordinate for node 1, minus one-third the y coordinate for node 6,

and minus one-third the y coordinate for node 7, and so on for the remaining nodes.

So I've basically setup these equations for the x system.

I said x1 is equal to zero, x2 is equal to one, x3 is equal to zero, and

x4 is equal to one.

And then I've set up these equations for the x coordinates of the remaining.

I've set up similar equations for the y coordinate.

So if I group these together, I basically position x1 and

y1 at the xy coordinates for node 1 at (0, 0), node 2 at (1,

0), node 3 at (0, 1), node 4 at (1, 1), and

I've set up these relationships for remaining coordinates.

Now, you might notice something here.

I'm basically saying that node 5 It's going to be node 1's position

plus node 6 position plus node 7 position divided by three.

So basically the position of each node is going to be the average of the position

of its neighboring nodes that it shares an edge with, and that's true for

all the remaining nodes.

And so we fix the position, we set the position for

some of our nodes and then the remaining are just

going to be set to be the average of the nodes that are connected to.

And so if I solve that system, if I solve that linear system you can use any

numerical methods you like to solve that matrix problem, you get the solution.

So that node 5 is at (1/3, 1/3).

Node 6 is at (2/3, 1/3).

Node 7 is at (1/3, 2/3), and node 8 is at (2/3, 2/3).

And so each of these nodes ends up being at the average, the position of node five

is equal to the average, the centroid of node one, node six, and node seven.

So I take node 1 plus the position of node 6 plus the position of node 7,

divide by three, and I get node 5.

So we've solved for these positions of node 5, 6, 7, and

8 to find this planar layout of this graph shown here in a non planar

embedding by solving a matrix problem.

You don't have to solve a matrix necessarily to do this.

You can do the same thing by basically starting with your nodes 1, 2,

3, 4 in their fixed position, and then for all the remaining nodes,

you can assign them random positions to begin with and then iteratively,

replace those node positions with the average of their neighboring nodes.

And if you continually replace every node's position

with the average of it's neighboring node's position,

those nodes'll work into place where they belong.

And so you can solve this system without setting up a matrix

just by constantly doing that iterative procedure

of moving every node to the average of it's neighboring nodes.

So Tutte's method tells us that we can solve a linear system to embed a planar

graph, but it's not that difficult.

You can do the exact same thing by nailing down

a few of your nodes into fixed positions.

And then the rest of the nodes,

you just replace their position with average of their neighbor's positions,

the positions of the neighbors that share an edge with that node.

If you keep doing that over and over, those nodes will relax into the exact same

position that tutte's method will converge to.

[MUSIC]

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados