Optional Lecture 3: Power Law Graphs

Loading...

Del curso dictado por University of California San Diego

Graph Analytics for Big Data

569 calificaciones

University of California San Diego

Graph Analytics for Big Data

569 calificaciones

Curso 5 de 6 en SpecializationBig Data

Want to understand your data network structure and how it changes under different conditions? Curious to know how to identify closely interacting clusters within a graph? Have you heard of the fast-growing area of graph analytics and want to learn more? This course gives you a broad overview of the field of graph analytics so you can learn new ways to model, store, retrieve and analyze graph-structured data. After completing this course, you will be able to model a problem into a graph database and perform analytical tasks over the graph in a scalable manner. Better yet, you will be able to apply these techniques to understand the significance of your data sets for your own projects.

De la lección

Graph Analytics

Optional Lecture 1: Bi-directional Dijkstra Algorithm2:00

Optional Lecture 2: Goal-directed Dijkstra Algorithm2:35

Optional Lecture 3: Power Law Graphs2:53

Optional Lecture 4: Measuring Graph Evolution3:41

Optional Lecture 5: Eigenvector Centrality6:47

Optional Lecture 6: Key Player Problems2:50

Conoce a los instructores

Amarnath Gupta
Director, Advanced Query Processing Lab
San Diego Supercomputer Center (SDSC)

So we have seen how to compute degree histograms of a graph.

While degree histograms are useful to characterize a graph,

it is usually a means to an end.

It's a known practice in statistics to compute a mathematical expression for

a statistical distribution Using histograms.

For graphs, we often look for a function to describe the degree distribution.

But this is expressed as a distribution of the probability

that a random vertex will have exactly k neighbors.

Now, this problem has been investigated by many.

One popular, well known model, is a Power Law.

A graph follows a Power Law if, the best probability is given by k,

erased to a negative exponent called alpha.

The value of alpha, for many practical networks, is between two and three.

More recently,

people have suggested other distributions that look like the power law graph.

One of them is a log-normal graph.

Here, the logarithm of k has a Gaussian distribution.

So this log-normal distribution seems to have the better fit to

natural graphs that are observed.

So, why are power law graphs important?

Interestingly, many very,

very different real life graphs in the world seem to follow the power law.

If a graph does follow the power law, it would have one large connected component

with a very high proportion of notes connected to it In a power law graph,

most nodes have a low degree and some nodes will be disconnected.

The low degree nodes belong to a very dense sub graphs and

those sub graphs are connected to each other through hubs.

In the center of the graph has a high density,

power law graphs can be difficult to compute with.

For example, the shortest path algorithm operating in the dense part

will possibly be very inefficient, not because of the size of the network, but

because there are too many paths to explore inside the denser pieces.

The more interesting reason why people study power-law graphs

is because power-law graphs are supposed to be robust.

So in nature, all biological networks show power-law graphs because

It gives you a high rate of redundancy against failure and attacks.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play