0:01

High folks.

Â So this is a lecture which is designed for people who haven't had much

Â background in social networks or working with representations.

Â So if you have had a course say course or Michael Kearns course.

Â If you've seen that course before,

Â then if you feel comfortable then you can skip this one.

Â But this is for people who really just want to get the real basics down of how we

Â represent these things.

Â And so, well I'm going to start with this just basic different types of network.

Â So generally we have some set of nodes, vertices, agents, actors, players.

Â So those are the objects that we'll be connecting via links and ties.

Â And between those individuals we have edges, links, ties,

Â you see many different terminologies in the literatures,

Â depending on whether you're coming from graph theory or sociology, or economics.

Â And they come in different flavors.

Â So it might be that they have intensity, they could be weighted.

Â So it might be, for instance,

Â that we're keeping track of how many hours two people spend together in a week.

Â And then it could go anywhere from 0 to whatever,

Â 7 times 24 is a 148.

Â And then we could also keep track of things like,

Â how much of 1 country's GDP is traded with another.

Â It could also be something where instead of having intensity,

Â we're just keep track of whether there's a relationship or not.

Â And we could think of those as unweighted.

Â So we have two people written an article together,

Â if they're researchers, or two people friends on some social platform.

Â That's either something that's true or not true.

Â And they come in flavors that could be directed or undirected.

Â So it could be that we're looking at mutual relationships, like co-authorships,

Â being relatives, being married, or it could be something where there's a one-way

Â relationship, so one web page can link to another without being linked back to.

Â They could also be that even one article cites another, or you could follow

Â somebody on a social media platform without having them follow you.

Â So there's different situations and

Â we'll represent these depending on exactly what we're looking at in different ways.

Â So if we are thinking of a simple undirected network, then we can keep

Â track of this either as what's known as the adjacency matrix.

Â So that's the g here which is g for graph generally.

Â 2:26

What we're going to do, is we will put in a 1 if the two individuals are connected.

Â If i and j are linked, then that entry will be a 1.

Â And it's undirected, so it's symmetric.

Â So here 1 and 2 are linked together, and

Â we have the g12 is a a 1 and g21 is a 1.

Â And that's indicating that these two individuals are linked together.

Â So sometimes we'll represent these things graphically,

Â sometimes we'll represent them in terms of adjacency matrix.

Â It can also be quite handy to just list the links.

Â So for instance, just keep track of a list of which pairs are linked together.

Â And in terms of notation, it will be a little easier not to carry around the set

Â of bracket notation all the time, but just say 12 are linked, 14 are linked, 24, 34.

Â And why would we want to represent things in this way?

Â Well when we start working with really large data sets, so

Â something that has millions or tens of millions or more nodes,

Â then keeping track of a matrix becomes cumbersome.

Â So it's going to be hard to put that into memory in a computer.

Â Whereas if we just keep track of the list of links that

Â economizes as quite a bit on what you have to keep track of.

Â And also in terms of our representation, sometimes there will be easier just to

Â think of sets of links rather than thinking of matrices.

Â But other times the linear algebra associated with matrices would be

Â quite handy.

Â So we'll flip back and forth between these different representations, and

Â g sometimes will represent a set of links, sometimes it represent a matrix.

Â Sometimes it will represent things graphically.

Â We'll be flipping back and forth between all three in this course.

Â 4:03

Okay, now in terms of directed networks, it's a similar situation but

Â now we don't have the symmetry, so it's possible that 1 is connected to 2, right?

Â So there's a directed link from 1 to 2, but the link from 2 to 1 is not present.

Â So we don't have the reverse relationship.

Â And so we still have an adjacency matrix.

Â We can still keep track of things.

Â But now when we keep track of this g, the order of things makes a difference.

Â So before if it was undirected, 14 meant 1 and 4 were linked together.

Â Now we have to keep track if there's a link between 1 and 4 in one direction,

Â and also back in the other direction, but

Â between 1 and 2 it only goes in one direction.

Â So now there can be asymmetries, and

Â the order of the actual nodes in a link makes a difference.

Â And there's different conventions, but

Â basically we'll be thinking of this as say the out degree, an arrow out from one.

Â So 1 is following 2, 1 is connected to 2, but 2 is not connected to 1.

Â So there's not something going back into node 1.

Â And that will be the terminology we'll use in

Â terms of a link going out from the node, or a link coming in to a node.

Â 5:20

Okay, we can also have weighted directed networks.

Â And when we get to talking about learning especially,

Â then we'll be looking at this sort of network.

Â And in particular what does this look at?

Â What does this represent?

Â So if we look at the picture here on our right,

Â what we have is a series of different nodes that have weights between them?

Â So in particular for instance node 1 is putting a third of its weight on 2,

Â a third of its weight on 3 and a third back.

Â So it weights everybody equally.

Â And we can think of this as if I'm paying attention to opinions and

Â I'm trying to form my own opinion.

Â I might be paying attention to the information that comes into each person.

Â Here, 1 is very democratic and is weighing everybody equally, 2 is

Â slightly different there, 2 weights one-half and two-half.

Â So 2 is not paying attention to 3 at all, but it's putting equal weight on 1 and 2.

Â When we look at 3 in this case, then we see that 3 is putting

Â most of the weight on him or herself, and only a quarter on 2.

Â And there's again, going to be an adjacency matrix in this case.

Â And here this is what we would call row stochastic.

Â And the situation where we're thinking really of weights that sum up to 1, so

Â they're all negative.

Â So somewhere between 0 and 1.

Â And when we look at the weights in this case they're summing up across each row.

Â So sometimes we will have weighted, directed networks.

Â We might be interested in stochastic ones.

Â So stochastic here, the sum of the gij across j is equal to 1.

Â So we have that row stochastic matrix.

Â 7:10

It might also be that the weighted directed network doesn't sum to 1.

Â So for instance here if we're thinking of the number of hours that different nodes

Â spend with each other.

Â 1 is spending seven hours with two a week,

Â 2 is spending five hours a week following 1.

Â 1 is spending two hours following 3 and so forth, or we could have hours here or we

Â could think of this as numbers of emails that are sent in one direction or another.

Â And they don't have to be reciprocal.

Â It could be that 2 sending emails to 1 and 1 sends more emails back to 2,

Â and here 3 sending them to 2, but 2 doesn't send them back.

Â So these are all different representations depending on which applications we'll

Â be looking at.

Â We'll be switching back and forth, and

Â of course one limitation here is all of these is static pictures.

Â So they're fixed matrices, they're fixed graphs, they're static in time.

Â Dynamics, we'll talk about a little bit in the course and

Â we'll be using these over time.

Â They might be changing, and so

Â we might keep track of these with time subscripts as well.

Â Okay, so this is just sort of basic background of how we represent things, and

Â now we'll talk a little bit more about representing networks and

Â what we can do with these kinds of representations.

Â