Loading...

Optional Lecture 3: Power Law Graphs

Course video 23 of 47

Graph Analytics for Big Data

Universidad de California en San Diego

Curso 5 de 6 en Macrodatos Programa Especializado

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.

Destrezas que aprenderás

Graph Theory, Neo4j, Analytics, Graph Database

Impartido por:

Amarnath Gupta
Director, Advanced Query Processing Lab

Transcripción

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.

Acerca de Coursera

Cursos, programas especializados y títulos en línea impartidos por los principales instructores de las mejores universidades e instituciones educativas del mundo.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

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.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play