Optional Lecture 6: Key Player Problems

Loading...

Del curso dictado por University of California San Diego

Graph Analytics for Big Data

571 calificaciones

University of California San Diego

Graph Analytics for Big Data

571 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, in this optional module, we'll look at the two key player problems again.

The goal of the first problem is to identify a small set of nodes,

whose removal will create maximum disruption.

Now, in this case, a traditional centrality algorithm may not work,

because the optimization goal is to break up the network.

So we need a quantitive measure of the breakage.

If dij is the distance between nodes i and

j, then 1 over dij is the closeness of these two nodes.

If we add the closeness of all nodes and normalize it by the number of node pairs,

we'll get a measure of cohesiveness as a fraction.

So, 1 minus this value is a measure of fragmentation.

Our goal is to maximize this fragmentation metric.

In the model terrorist network shown here, removing the red nodes A,

B, and C will break up the network into seven components,

with F reaching a value of 0.59.

The second key player problem, is trying to find a group of S influencers,

which can reach a maximum number of nodes within K steps.

The number of unique nodes reachable from a starting node is called the reach,

of the starting node.

For this we need to adapt the concept of reach to limit it to k steps.

We also need to adapt it to measure the distance of an arbitrary node

from a group of nodes between our influences.

The distance from one node to a group of nodes can be defined as a maximum,

or average, or minimum distance, of the node from the members of the group.

Often, the minimum distance is a good choice.

So the distance, we could reach,

can then be through of, as the proportion of all nodes reached by the group,

where the nodes are weighted by the distance from the set.

And only nodes at distance 1 are given full rate.

Hence, a distance we could reach that use a maximum value of 1,

where every outside node is adjacent to at least one member of the set of influences.

In the network shown, just three nodes, A, C, and D,

are sufficient to reach every other member within just four steps.

Now this concludes this module, where we looked at several analytic techniques and

measures to extract different kinds of insights from a network.

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