Warm up algorithm 1: Extracting egonets

Loading...

Del curso dictado por University of California San Diego

Capstone: Analyzing (Social) Network Data

81 calificaciones

University of California San Diego

Capstone: Analyzing (Social) Network Data

81 calificaciones

Curso 5 de 5 en SpecializationObject Oriented Java Programming: Data Structures and Beyond

In this capstone project we’ll combine all of the skills from all four specialization courses to do something really fun: analyze social networks! The opportunities for learning are practically endless in a social network. Who are the “influential” members of the network? What are the sub-communities in the network? Who is connected to whom, and by how many links? These are just some of the questions you can explore in this project. We will provide you with a real-world data set and some infrastructure for getting started, as well as some warm up tasks and basic project requirements, but then it’ll be up to you where you want to take the project. If you’re running short on ideas, we’ll have several suggested directions that can help get your creativity and imagination going. Finally, to integrate the skills you acquired in course 4 (and to show off your project!) you will be asked to create a video showcase of your final product.

De la lección

Introduction and Warm up

Welcome to our capstone project! In the last four courses in this specialization you've learned many core data structures and algorithms, and applied them to three different real-world projects. In this capstone project you'll be doing a project very much like the projects from these other courses, only it will be almost entirely directed by you! In this first week you'll get warmed up by playing around with the data that will form the backbone of this project: social network data. Then you'll get back into writing code by implementing a couple of graph algorithms to answer questions about this data.

Introduction to (some) social network data7:10

Representing social network data as a graph2:30

Warm up algorithm 1: Extracting egonets3:12

Warm up algorithm 2: Strongly Connected Components5:11

Warm up algorithm 2: Strongly connected components, part 210:34

Conoce a los instructores

Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Leo Porter
Assistant Teaching Professor
Computer Science and Engineering

[MUSIC]

Okay, once you have your graph all constructed and you can hold your data as

a graph, let me tell you about what you're going to do with that data.

The first task you have is to implement that getEgonet method that I showed you.

So by the end of this video, you'll be able to describe what an Egonet is, and

an algorithm you can use to extract it from a graph.

So let's take a look at this little chunk of a Facebook social network graph here.

Got a bunch of users here and

they're connected to each other with friendship relationships.

And you can see some patterns in this graphs,

some things to note about this graph.

For example, one thing that you note is that not

everybody is friends with everybody else.

Of course, not everybody is friends with everybody in the world.

You have this group of friends, and moreover, within your group of friends not

all your group of friends are friends with each other either.

So for example, 25 is friends with 23, 18 and 65, but 65 and

18 are not friends with each other.

So that's a couple of things that you can notice.

And a question that we might want to ask is

what does a given user's group of friends look like?

How connected are they?

What are their relationships, how big is it?

And we might want to ask a bunch of questions about a particular user's group

of friends.

So we're going to define the concept of an Egonet.

An Egonet is just a subgraph of a larger social network graph

that's essentially centered on one particular user.

It includes all of their friends and then relationships between their friends.

So for example, let's take that node 25 again and look at the Egonet for 25.

So the Egonet for 25 is going to include the nodes 23, 65, and 18.

Because of the fact that 25 is directly connected to each of these users,

via a friendship relation.

But it's also going include this edge right here between 65 and

23, because 65 and 23 are also friends.

So that is the complete Egonet for 25.

And you can see it's a subgraph of the entire graph.

So we can get rid of all the other nodes and edges, and

we're left with just this Egonet.

Actually, before I go on to tell you what you're going to do in your assignment,

the method you're going to implement,

I'm going to have you practice this a little bit on your own.

So what I want you to do next, is I want you to extract the Egonet for user 50.

All right, so hopefully you were able to do this without too much trouble.

So starting with user 50, we want to gather all of their friends,

all of the users that they're directly connected to with a friendship relation,.

And then all of the edges, all of the friendships between their friends.

And we want to get rid of everything else, and

that would be the subgraph that represents the Egonet for user 50.

So, in your assignment,

what we're going to ask you to do is implement this method called getEgonet.

It takes an integer which is the center of this Egonet,

the person that we're talking about.

And then it returns a graph, and it should be a new graph object which contains

only the nodes and edges for the Egonet for this particular center user.

So shouldn't be too bad,

this is your warm up assignment and we hope you have fun with it.

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