all right so today is our last lecture
in in in this module and we'll talk more
about community detection so lecture
outline will actually discuss bunch of
very very different methods we'll talk
about overlapping communities and ways
to detect overlapping communities
through what's called click percolation
method then we'll talk about several
heuristic methods those that well
sometimes they optimize something
sometimes they just think two things is
sort of heuristics and there are sort of
two most well-known one is called label
propagation which is extremely simple
method and the other one is fast
community unfolding it's actually a very
very popular method and finally we'll
talk about methods based on the random
walk ideas there are two algorithms rock
trap community detection and kneeble
they're very different in the way they
use a random walk in fact walk trap I
believe came from physicist nibble is
from hard core computer scientists and
out of all the algorithm that we're
going to talk about day Nebo is the only
one that has actually all kind of
convergence guarantees and and like well
honestly lots of math behind it last
time you guys looked at also add this
mcl method that is well use this ideas
of random walk in it so you would put it
probably into the same cohort as random
walk methods but there is something else
that that unites this methods under
number three and it's the fact that this
method methods can be used locally and
so the
very very powerful when we deal with
large graphs um so the idea there is
that you can actually detect communities
and maybe it's single community if you
want to cut it out from the graph but
with a time proportional to the size of
the community now that's a very big deal
because again if you have a million node
graph and you're interested only in a
few communities in that graph we don't
want to mess around with the entire
graph okay so that's the plan for today
so a couple of words about the in
general about community detection so we
we actually previously we looked at
sorry not writing okay so previously we
talked about so about two different
methods of community detection one
method was based on the vertex
clustering when we looked at the
vertices at the connectivity structure
between vertices decided which word is
which vertices are similar and then
based on that we literally just used
standard clustering algorithms and in
fact we used a hierarchical clustering
to group them together
another approach was algorithm based on
graph partitioning and last time we
talked about bunch of metrics that you
can do that you can use they all um
depends on the sparsity of the cut and
cut is the number of edges you need to
remove to separate nodes and we talked
about minimal cut we talked about
normalized guard we talked about the
ratio cut but they all deal with
actually removing edges and if we look
at the picture
at this picture on the left it's very
clear that with this type of the
community is yes you can cut out
connectivity here they are there here is
you to three clusters of three
communities now if you try to use say
standard graph cut methods here here on
this picture there might be some issues
because we can clearly find this cluster
but there is really nothing to cut in
here because no D is connected to it
tightly to you know the green click and
create a coupled with the blue click and
so intuitively we understand and
actually not only intuitively but even
from the fusion of the clicks we
understand that this is a cluster
there's a bunch of nodes that are
tightly connected between them with and
with the rest of the ground so they are
a cluster but on the other hand this is
these are also a cluster so in fact no D
lays on the intersection of two clusters
and the idea of graph cut is not gonna
work here so you need something else to
be able to split this up to pull out the
dis clusters of this communities you
know one way one tricky way to do this
it could be like for example take this
node D and you know duplicate it right
and it and get one copy going to one
class to another to another and then you
get an edge between it that you could
cut but then the question is how to find
which nodes to duplicate so it's it's
obvious that to solve this problem we
need somehow different algorithm that
just simple graph partitioning now
vertex clustering the similarity method
I'm just again applied you will not be
able be able to apply it directly simply
because in regular clustering you all
sir assign a node or or a data point to
one of the clusters it's always
exclusive now
if you remember you're probably done in
data mining you can also look at not
only the exact clustering but also the
fuzzy clustering where a probabilistic
clustering where you can assign the same
data point to several clusters
well that method could be used together
with verdict similarity to do community
detection overlapping communities um
will actually consider somewhat
different methods that really really
sort of graph specific method for
community detection sort of in the case
of overlapping communities and here is
an example for now I'm in fact
overlapping communities are very very
very often if you just think for a
second you know about your facebook
graph I'm sure you have among your
friends you have people you know you you
went to high school together or then
there are probably people that that
we're with you as the University and
their hobbies etc etc etc and so if you
if you look at this egocentric graph
where you were like in the very center
well you know you might be that's the
point of overlap for this various
communities well there might be more
overlaps might be other people like you
but you know for you it's very clear
that your friends can come from
different parts of life and so you know
for social network this overlapping
communities are very very very common so
what we would like to be able to detect
eye situations like this right so you
might have for example for two
communities and let's say there is this
one community and it's not a community
because we want to detect to be able to
detect situation when there are single
node overlap in between them or when
they're say two nodes and that means
that there is an age overlapping or we
can have in a much much bigger overlap I
have multiple nodes overlapping from the
different communities and then overlap
those over nodes and over edges
so the algorithm going to talk about the
this k-clique community or k-clique
percolation was proposed was proposed in
2005 by pi and coworkers so the idea is
the following they need is the following
let's take a look at the graph here on
the left it's well the graph is designed
to actually illustrate the algorithm the
point here is a following if we look
carefully say for example at this for no
we realize that they do form a clique
because and I click if you remember is
complete complete sub graph
it's a clique of size 4 there are 4
nodes and each is each of the nodes
connected to two other node now if we
look at this for no they also form a
clique each of them connected to all of
its neighbors if we look at these guys
this is also a clique right so we can
keep looking and say there is 1 1 2 3 4
again all these nodes connected with
each other and so it's also click and
finally you know these guys also form a
clique right now this might not this is
sort of carefully designed graph to to
have this property but in very many
cases you would actually see this type
of overlaps of cliques so the idea is is
the following this is a definition the
waters of the paper came up with the
called a key click community union of
all K clique
that can be reached from each other
through the series of adjacent gay
clicks and 2k clicks I said are called
adjacent if they share K minus-1 notes
alright so the idea is the following
said if you have a click here and let's
say this is a K click which means it
consists out of K nodes and you have
another K click here then you would have
overlap that consists of K minus 1 nodes
and then this 2 K clicks will be called
adjacent and if there is no more K
clicks overlapping with them they will
form a community right so the idea is is
if the following that community again is
a very very tightly coupled a bunch of
nodes but you might not we will we saw
this couple lectures ago that in real
life you don't have that many sort of
large clicks so what you might think up
is you sort of relax that definition a
little bit and call a key click
community Union of smaller actual
cliques so the community is a union of a
bunch of clicks and you define it as a
community if overlap between the clique
is pretty large and you know particular
this author's decided that if community
consists for example is out of four
nodes then they would like to have an
overlap of the size of three or if
community will consist you know
click-click consists of ten nodes then
they would like for two neighboring
clicks cake to neighboring cliques to
overlap on nine of those nodes so in
some sense you can think of this as if
you have some sort of template of the
size of four nodes and you can kind of
start shifting it and it covers your
clicks and and it every time you shift
it you kind of remove one node and and
add one
- this okay okay
so this is just a sort of formal way to
say that within a you know larger
community will have sort of will have
clicks inside that are tightly tightly
connected but the entire community might
not necessarily be all connected as a
real click does this make sense what
they're doing okay cool so then then
there is a sort of here's your way to
detect
overlapping communities right you can
you know find this Kay clicks calculate
the overlap between them you know find
the union of those clicks and call them
a community now in fact if you look at
this picture or what we have done here
we pretty much done the same thing
eventually we'll have two communities so
there is this one community and there is
another one community and they will be
overlapping over this node F now why we
don't join them together in one Union
well because each of this cliques that
are being used are of size four right
this sort of template is of size four
nodes and the overlap here is of the
size of one and so this is not enough
overlap according to the definition to
form a K clique community they will need
an overlap of size three or four these
two guys to be joined together and
that's why you know when you do this
eventually you will have two communities
so that's a that's the whole idea
now where is a catch here so what's what
can be a problem any ideas
how many of those cake cake cliques are
out there remember we talked about it
that if you actually try to enumerate or
try to go through all of them when you
finding so the way to detect cliques is
you need actually to go through like
literally one by one through nodes and
measure connectivity right so it is
number of in order to detect this in
sort of brute force fashion it's really
number of combination of how many ways
you can you can select for no it's out
of total n nodes so factorial large
number if you just brute force Li want
to go through this whole thing you know
it's factorial and it's impossible
so that that is sort of there the real
problem with with this method so but
there are good news there are good news
so what you can do is instead of just
using a clique um you can start looking
at a maximal clique which is if you
remember it's a clique that you cannot
enlarge and though finding again maximal
cliques in in a dense graph is again a
factorial large problem if the graph is
sparse your graph is sparse
there are algorithm that that do this
very very efficiently so sometimes
almost in a linear time of the open
number of nodes
well it's all scaled with with the
degree of the largest node but it is
doable now there's no good theoretical
guarantee is in a sense that in the
worst case in the worst case that the
performance is is really bad but on
average for like real real world graph
the performance sort of a and if it's
for small graphs
you can easily do this so here is
algorithm find all maximal cliques and
you can use the waters propose their own
way to do it or you can use pretty
standard for now algorithm to finding
maximal cliques that is based on sorting
nodes based on the degree then after we
detected all the maximal cliques let's
say these are maximal cliques we'll
create click overlap matrix well click
overlap matrix will just tell you how
many nodes lay on the intersection of
two cliques and then we threshold this
matrix at the value K minus one where
the K is that that number that we're
looking for so it will be that K click
and enter the result the communities
will be the connected components in this
graph so here's an example here's what
that's gonna look like instead of so
instead of literally starting with
clique of particular size we are looking
for maximal cliques right right
so the graph is two composed in two
maximal cliques and on this picture
they're color-coded and so you can see
that again I want to remind you that the
maximal clique is a clique that is not
our sub graph of a large clique right so
it's a clique that you cannot increase
so for example this is a clique right
but it's alright
if the graph is like this it's also a
maximal clique because for example this
top node is not connected to everybody
else so this is a clique and the maximum
clique but if we had this type of
connectivity then the maximal clique
would be um
already this whole thing okay so what's
done is we calculate we'll find all the
maximal clique in this graph and if you
look carefully they're color-coded and
for example here is one maximal clique
which is a triangle here is a clique of
size for maximal clique here is another
maximal clique so overall there are five
maximal cliques okay so if you want to
compare this algorithm you just find all
the maximal cliques and then you
calculate how many nodes are on the
intersection of those two maximal
cliques let's say there is one click
another click there are three nodes here
so it was click say you know one and
this is click 2 then on the intersection
then we build this matrix a no
intersection of one and two we could
number of nodes where those two maximal
clique intercept intercept so here's a
point right on the diagonal what you get
on the diagonal is just the size of that
clip and for example clique number five
is prime straight clique that the blue
click click and and the red one
intersects on over three nodes and say
the blue one and and the yellow one
intersects at three nodes okay and so on
so that is sort of click overlap matrix
the size of this matrix is number of
maximal clique by the number of maximal
clique maximal cliques and then you can
decide on the the size of this sort of K
clique for and the authors by themselves
tell that ok well it's usually three to
five a little bit bigger but not more
and what you do is you threshold this
this matrix by replacing all the
non-diagonal off-diagonal elements if
there are less than four we replace I'm
sorry if you're less um you remember we
need to we need we're looking for
overlap of size K minus 1 right so if k
equal to 4 are we comparing to number 3
and if it is less less than then then 3
we drop it and if it's more or equal to
3 we keep it and just put here 1 as a
you know as a sort of placeholder right
instead of instead of actual number the
the advantage of actually doing maximal
cliques is not only in the fact that
there are fewer of them but all sir if
you do it once you get this matrix and
every time you want to change K you're
dealing with the same matrix you do not
have to recompute this maximal clique
overlap matrix if we actually try to
compute clicks by themselves every time
we change K we would have to look for
different cliques here it's a maximal
clique so it's sort of K independent
then we calculate this matrix and then
we just threshold and if we want to you
find smaller communities we can go and
say okay for k equal 3 less threshold
everything that is greater than then
number 2 or if you want to community is
larger okay let's select k equal 5 then
the threshold value will be 4 so it is K
minus 1 overlap all right and I've we've
done that this think about this as an
adjacency matrix where every of node
came from click and then we can look for
connected component in this adjacency
matrix or you know in this sort of super
or click based graph and and in this
particular case they're actually two of
them
well that's pretty much it and that's
your - that's your - two communities one
community is this smaller one and the
second community is is this the rest of
the graph so that's sort of the this is
the idea of algorithm again for you know
small graphs there is no problem
whatsoever it works like magic for
larger graphs it really depends on if
the graph is sparse there is a good
chance that you can enumerate and
detectable maximal cliques in almost
linear time and then the only sort of
problem with this algorithm would be
that you actually need to write down the
matrix of overlap between those clicks
and so if there are a lot of maximal
cliques well that's a big matrix so
that's you know a lot of storage but
that's about it
other other other than that it scales
and of course you know if you don't want
to store that you can just recompute
this so you can make this algorithm
scale but you know depending on on the
on the data set you might get unlucky so
here's a couple of examples the waters
show of the over there algorithm how it
works in real life so on the Left do you
see there
small graph of currents of words and for
example the word play car curse here in
a different context it's used if you
notice this graph is really about music
these are about I would say you know
kids playing toys and this is maybe
about right it's probably theater or
movies yeah theater topics and and so
the same word is used in all three of
them and regular clustering
community detection will not be able to
place it you'll have it would have to
place it into one of those topics but
here it can it can leave there sort of
as an overlap for for communities now
here communities overlap on one note k
equal to four so the threshold for four
for the Union for those it clicks is
three and so one is less than three so
you know there and that's why they're
not merged together but they overlap on
one now on the right hand side the
results are analysis of some program
where the notes are the variables used
in that program and how they occur
within the sort of function calls here's
the interesting part is that you can
also see there are some overlaps here
but what's interesting here there is
overlaps like pretty big overlaps here
they're there they're shown in red color
um for example here the size of the
overlap is three now these are sort of
big communities big clusters K was equal
to 5 and so 5 minus 1 is 4 and and again
this overlap is of size 3 and so it's
not enough to merge that purple and and
and and brown communities into one so K
is is a very critical parameter right
depending on K you'll get you might get
quite different pictures over the world
and here's another example from their
paper - I love the paper because you
know really pretty pictures
so what's shown here is again the subset
so there's a big graph this is sort of
super graph it's a graph of communities
and there is a zoom in here and you
realize that there is a bunch of
communities you know what's shown on
this big graph is every node on
big graph is a community it's
color-coded accordingly so you sees for
example brown community here's brown
community here is a green community
here's a green community the size of
that node is proportional to the number
of nodes in the community and you can
see that some of them do overlap like
for example there is this brown
community and there is yellow community
well there is brown note yellow note and
they have a connection in this super
node or or click graph now they're not
merged together again because the
overlap is just in one node so that's
why they remain separate communities um
and then you'll get the sort of the the
sort of the two-level picture
representation of the graph where this
is a sort of community structure of the
graph and here of individual communities
so that's this K clique calculation
method any questions about it okay
just if you excuse me one second all
right so let's move on the second
algorithm I want to talk about today is
actually very very simple
it's called label propagation now here
we're not talking about overlapping
communities anymore we're just trying to
do community detection and and here idea
is you know really really reminds you of
of things like in an classification um -
you guys are you familiar with CNN
so what was the sort of main ID in the
canine classification all right
excellent we're familiar but we don't
remember exactly
well okay Anna means eight nearest
neighbors right so what's the idea so we
take labels of the nearest neighbors and
then decide on the label of the node
based on the nail labels of the nearest
neighbors right so in KNN you typically
assume that there are some points in the
data with given to you labels and then
some other data points you want to
predict labels on and use those labels
that I that are known to predict the
labels of unknown nouns right so there's
one sort of algorithm which is which is
similar to what we're going to talk
about another algorithm which I'm sure
you're familiar with is kmeans remember
that one I'm sure with buddy's Grigory
which you should know this really really
well so that's another algorithm which
allows you to in some sense real label
nodes right in that algorithm you take
initial labeling of the nodes as
belonging to different clusters and then
you charitably update the distribution
of nodes per cluster until things
converge all right so label propagation
algorithm here is is really really in
spirit very very similar
it is heuristic method every step and um
so the way the way this work is is a
following so at first we initialize
labels we initialize every node to its
own label okay it just can be like a
node now
um and the one little trick here is to
randomize order of the nodes and then
you just literally sweep through all the
notes and for every node replace its
label with a label that occurs the
highest frequency among its neighbors so
it's sort of a majority vote okay
and the idea is the following that
within the cluster all knows connected
to each other
and then eventually they will converge
to the same label now if by whatever
reason you have a tie which means you
know equal sort of votes four four four
nodes well you know you break this tie
at random and you know if the
situation's saturates which means you
know they stopped changing you know we
start out with or you can stop it sooner
if you know the note has a label of the
maximum number of neighbors so here is
like little little example how this will
work on the clique
I mean if it doesn't work just purely on
the clique you know it's not gonna work
on anything else right so need to make
sure that this this this idea works for
elite here is an example of a clique we
start from the left to right every node
has its own label 8bc ABCDE and let's
say you start with a node we start with
a note here we start with a node say C
okay
so what happens is node C has three
neighbors D a
and be so all three Labor's have
different I'm sorry all three nodes all
three neighbors have different labels so
according to the algorithm we just
randomly you know pick one of those
labels okay and we change the label on
the note C to be a well then what
happens after that is very simple we
said we take another node let's say node
E now node E has a majority vote a
already because has two neighbors that
are a type so that means we change label
nope it also to what's left I know it's
D and B well now again for know D the
majority of the knows Ally have labels
aides one two three nodes out of four
and for B it's also majority is a so
eventually the entire quick got the same
label alright alright so that's pretty
much it it's it's very now this album
actually became very popular because of
its simplicity it's really linear
because you know what you have to do is
just go through all the nodes it might
take several iterations and until the
thing converge this algorithm amazing in
the sense that it doesn't optimize
anything there is no you know there is
an optimization function that there is
no optimization method we just sort of
play this game of type of KN you know
just replace the labels so it's very
easy to implement and it's it's is it's
very easy to run now there were of
course situations when this fail and
there are some very particular issues
with this algorithm you can look at the
original paper and the papers after that
but one of them is it seems that
algorithm tends to detect very very
large communities so it is not sensitive
to small
communities if it can detect large one
it will detect large one so for example
if you run this algorithm on say random
graph it will literally pick up the the
giant connected component I'm sort of
you know label the same graph this
anyway um I couldn't I couldn't find a
you know good example in in the original
paper but she reappears at here's
example from one of the online blogs
that is dedicated to network analysis
this is if this looks like a like the
world to you well it is the world right
here is you know Europe somewhere Russia
Africa u.s. thousand America China
Australia so this is a flight data it's
you know airports and the flights
connecting those airports and so what
was done here the others tried to run
community detection one on the on the on
this data without knowing the geography
of the airports and just running
community detection to see if the
airports of say the same country will
group together well I mean it's it's
reasonable right because if you think
about this they're more flights
happening within us then that connects
us to the rest of the world so they're
probably US airports are more tightly
connected between themselves and with
and with the rest of the world um the
results of some hierarchical structure
if you remember you know that with
airports the way things are organized
from major airports major hubs and then
there are smaller airports that connect
it on it to those major hubs and no wear
out and and so um but hopefully in the
data set there are also geographical
coordinates so what they try to do is
after that after they did the clustering
they they mapped the airports to the
actual geographical location on the map
and just to make sure you know the
coloring that comes from node from
community detection is consistent with
actual geography and energy is
but if you realize what happens the
label propagation method was not able to
distinguish sort of subtle communities
and here it merged all us together well
it couldn't it couldn't filter out
Russia for example right there is this
whole you know blob of Europe there's a
whole blob of China so it is this issue
of of this algorithm of being able to
detect and in your eight very large
communities and well as as with a lot of
here we see without written there is no
guarantee so you know it can run on this
data set will not run on other data set
but the good news it's very cheap it's
easy to implement and it's cheap to run
so we can actually just try it and see
if this works any questions about this
this one I mean as always you know
heuristic algorithms are are either
extremely simple or extremely
complicated and bizarre but that wasn't
the algorithm here is not the one here's
another one this is called fast
community unfolding this is in fact a
very popular algorithm it is also
heuristic but it is sort of you know it
called step up here is stick in the
sense that we're actually trying to
optimize something now we're doing it
you know not not the the sort of the
classical optimization way to be doing
it through some heuristic which fact
just doing some sort of local greedy
optimization which means we're not
achieving that the real maximum or of
the function we are optimizing but you
know we're getting in that direction so
in this algorithm it is clear that there
is a function we want to optimize and
this function is inspected again
modularity and you know we talked about
modules in many time many times so this
is a compare
of the connectivity within the cluster
versus the connectivity in a random in a
random graph and the idea is again to
find partitions of the of the network
into the communities with the highest
modularity now the cool thing about this
one it actually merges the idea of
optimization and the modularity connects
this idea with multi-level hierarchical
scheme well in fact I would say not to
level schemes are probably the most
powerful schemes that are out there you
know if you're familiar with linear
algebra in linear algebra there is a the
method which is called multi grid multi
grid algebraic multi with linear algebra
there is multi grid for solution of
numerical solution of P DS the analog to
this in signal processing wavelets
so it's multi-resolution representation
right and an algorithm that are capable
of using that they are very very
efficient again because the this is the
same notion as divide and conquer so
every time you kind of split the data
split the data split the data and you're
really quickly to like log n steps
getting to like very small things so in
some sense this algorithm usually have
like sort of n log n type of performance
and and because of their
multi-resolution nature they can also in
this case detect clusters of different
size so it's actually this is this is a
very powerful method it also called you
know sometime like Lorain method because
of the university where all the authors
were at that time um you know you could
either look for fast community unfolding
all of a map so the idea is the
following and again this is remember
this is heuristic method which means see
them does make sense to ask why they do
it that way right but there is some
intuition but you know they decided they
tried it it works ok well run with it
so here's that here's algorithm we
started also exciting every node to its
own community yeah and then there are
two steps in this for every node so the
algorithm goes through every node and in
that evaluate modularity gain from
removing the node from its own community
and placing into the community of the
neighbor so on the very first step if
every node is in its own community and
remember it calculated at home the
scores the modularity scores for the
different communities daddy is the
following I'm at first we consider every
node to be in its own community let's
say we're looking at this node this node
is its own community but then we decide
ok let's see if we change label ok let's
say this is another label ok this is one
more label so we have every node starts
with its own label and then what we do
is let's say on on it on a step one
we'll take this node and decide to
change its label to the label of its
neighbor or evens out in other words
join the community of the neighbor and
change this label to green if we change
this label to green the modularity score
will change because now there are two
nodes that are connected and they belong
to the same class so the modularity will
change
so if the modularity increases will keep
this change if the modularity by when we
do this decreases will not accept this
change and then of course when you start
getting sort of bigger cluster see the
bunch of greens there is this new guy
again we can either connect them change
the color or not and what we do is we
repeat this iteration until until you
know the the modularity increases now
it's very clear that you know this is
not a global optimization scheme which
means depending on how you're gonna run
this in which order you go through the
notes you might get different modularity
scores and different final distribution
okay but you choose one and you optimize
within that you know ordering and in
this sense you will get local maximum of
modularity local in the sense that it is
not you know the maximum possible
modularity you can gain for this graph
but it is the best that you can get for
this type of procedure okay and after
you've done that you go to the second
step the phase two where you actually
merge the notes from the community into
one super node so out of this picture
will get say one super node of green
color and say there is there is still
the black color and then let's say okay
let's do towards red here so a red color
and this is graph of super nodes each of
them has been detected by this
modularity thing right of them is
actually aggregation of bunch of nodes
um and the way and and we'll also get
weights on edges all right and then what
we do will just follow through and you
know repeat phase one
but now on this super graph and we will
build on and build a silken sequence of
this graphs and so we'll create this
multi-resolution scheme we're on the
very first layer we have you know the
real nodes and then on every next layer
after that we're actually combining you
know communities into larger communities
all right make sense can you actually
implement this yeah you should be able
to because the modularity you know how
to do modularity the only trick here and
I would if you're actually interested in
this method I would refer to the paper
is how to calculate the change of
modularity when you move node from one
cluster to another you do not want to
recompute the whole modularity of the
entire graph there is a way to actually
it efficiently implement this local
change so you know just to reiterate
that's what's happening
looking at the nodes and it's signed
down to different clusters based on the
modularity right and and you again we go
like starting from every node being in
its own cluster and then trying to merge
with neighbors and you know except this
merge or accepted but not merge but
except that the label of the neighbor if
that increases modularity and eventually
you will see that that in particular
this graph you got this red nodes green
nodes blue nodes again modularity is
calculated as as we compare the scoring
based on the actual edges versus a
random graph so afterwards
that we can create a graph of super
nodes where every super node is you know
was a community here so there was this
green community that's one super node
there was this blue one another one red
one hue the third one and we put weights
on edges this is number of edges that
connects those communities in the
original graph for example green and
blue there is number four well there is
this one H two three four and there is
the size of the communities and then
we'll run exactly the same algorithm but
now on this graph and eventually we get
this picture so that here are three
layers three levels you know we got
quests cluster ization
or we got communities and and here is a
really pretty picture um that shows this
is some artificial sort of fractal like
multi-resolution graph that shows you
you know how the algorithm detects
communities and how in a different level
it can actually pick up you know in the
first iteration to pick up say this
community is and then a bigger scale
they will be merged into that community
and on a larger scale that community
becomes that one so it's really
multi-resolution thing and you know you
can compare this to say the results of
the label or the label propagation
algorithm that just creates for you you
know simple and playbook simple labeling
that dominated by large clusters so this
one actually can go into details right
and and create the sort of levels and
again and the great news that it is
really efficient it's computationally
efficient and and so it's for many cases
and in the method of choice these days
if you want to do our communities and
large graphs any questions
okay so this is actually you know this
is this is a very good method though you
know no guarantees for the convergence
okay we're going to switch to the last
topic which have several algorithms that
are based on random walks now here we'll
have to get back a little bit to some
mathematics I'm not gonna prove anything
but still you know give you hope give
you some sort of um feel on why this
works so that the first that the first
algorithm is called a walk trap
community detection goes back to 2006
the idea is you know well it means you
can see the random walk but what makes
this algorithm a little different is the
following so the authors want to
consider random walk as a tool to
calculate similarity between nodes of
the graph so if you remember we started
this whole story with network with
community detection with graph
similarity algorithms where we said okay
well let's look at the nodes and and
find how similar they are based on the
structure well and over there we
literally sort of brute force Li Lu used
the the nearest neighboring structure to
find similarity between nodes now there
were some ideas also to for example use
you know the shortest path and and call
two nodes similar if they close to each
other
in terms of the shortest path but this
doesn't work too well in in the real
graphs well by the way but why do you
think that did do why wouldn't the
distance metric based on the shortest
path between nodes why
wouldn't it work I mean what's wrong
with that metric so imagine that I want
to I want to calculate similarity
between two nodes in the graph and I'm
proposing the following idea
let's call two nodes similar if the
shortest path lengths between them is
small so will that work
any ideas so again I'm considering some
graph and I want to to do eventually you
know clustering or community detection
and to do that I want to use this the
node similarity ideas and you know I'll
group together those nodes that are
similar and as a similarity metric I can
for example do something you know one
over the shortest distance between nodes
and I would say okay well if the nodes
are close to each other it means that
that they're not far apart to the
shortest distance is small that means
they're very similar will this work mm
okay um yeah well the triangle
inequality means you know if we do it
with distances you could do it with
similarity we don't care that much about
it but here the answer is simpler than
that you know you can actually do that
there is nothing wrong about it the
problem is that if you remember in real
world networks in the networks we're
dealing with what do we know about the
damage of that Network what what kind
network they are there a small world
network remember six degrees of
separation right it's even with a
network of a several a billion nodes
the average distance between nodes will
be five or six and that means that using
simple distance between nodes will not
be will not allow us to differentiate
among a lot of clusters because all the
nodes in this type of networks are very
very close to each other so this this
distance type of metric will work if we
deal with geometric Ravel let's say we
deal with a graph that describes you
know road network but it will not work
for the social network it just does not
have the this is the the similarity in
this case will not have enough
differentiating power to distinguish
notes and distinguish clusters so
instead of that um what people decided
to use is what's called diffusion
distance so instead of actually counting
the shortest paths between nodes we
calculate the distribution of the
diffusion starting at a particular node
and diffusion means you know random walk
and so the idea is the following when
you start a random walk for a particular
node it can go you know uniformly at
random to each and every neighbor and
there is a probability that random walk
in one step is on the neighbors and then
there is a probability that random walk
in two steps either here there there or
there so when you start diffusion there
is a probability that after one step
after two step after three steps the
diffusion walk is on one of the
neighboring nodes and it's really
diffusion because initially it starts
with the probability being one on the
node you start from um n zero everywhere
at the first step then it sort of spread
around then it spreads and spreads
you know and eventually after a long
long time it will actually go to to some
particular distribution now it's
actually very well known that for
undirected grab the distribution the
probability to be on a particular node
will be proportional to the degree of
that node you can actually show this for
n the wall but we're not going to look
for that sort of long time intervals
what we do is we can see there are few
steps and the idea is the following
we're going to define the distance
diffusion distance between two notes or
or random walk distance between two
nodes by comparison of distribution
probability distribution of the random
walk that starts from node I and starts
from node J and we can pair those
probabilities on node K which are
neighbors and we sum over all those
neighbors and the trick here it's also
normalized by the degree of the node of
the nodes K now there is a theory why
you do it the sort of the intuition
behind it is you do it because um the
the nodes with a high degree because
they have more incoming edges they have
much higher probability to get random
walk to come to them and you want to
normalize it out but I just want to just
take it as sort of a definition so what
you do is you compare the distribution
of the random walk with the probability
of the of the random walk when started
from node I to end up on the node on
another node K and the idea is the
following they if the nodes are in the
same community let's say we have there
is a sort of tight community structure
and and and then say the reduce picture
up let me take another color
let's say we have diet community and
then we have another one so the idea is
the following that whenever you start a
random walk from the nodes in this
community whether you started from this
node or whether you started from that
node the probability to be is on this
node will be very similar
whether you start random work walk from
this node or if you start from that node
okay and and because of that and it's
not only to like outside nodes but also
to of course the probability to end up
on this node or the probability to end
up on this node and and because you're
summing up those probabilities those
nodes that are in a similar sort of
structural place in the graph they
provide very similar patterns of
diffusion so in some sense it doesn't
matter where the diffusion start within
a cluster it look will look very very
similar that happens because again every
node is very very tightly connected to
every other and so based on that you
measure the distance between two nodes
as a sort of diffusion distance based on
the distribution that those that the
diffusion from those node creates now
the parameter here is a number of steps
in the diffusion um
again if you know even if we take time
go to infinity then the distribution
over over the nodes will not depend on
the starting condition it will just be
proportional to the degree of the sort
of final node right that's a Markov
chain thing but if you take a few steps
there will be differences and this
difference I used as a metric as a
distance metric so there are two ways to
do this computation
one way is you actually just take the
matrix the adjacency matrix
well converted into the matrix the
matrix that describes random walk into
the random walk matrix and it's
converted by normalizing out and making
its what's called Rho stochastics and we
talked about this we talked about it
when we discuss PageRank so and you can
just take it to the put it to the nth
power or to the power T and that will be
your probability to end up on the node
after he stems now the trouble with this
the trouble was this is well it's it's a
large matrix you need to do this in a
large and in a large matrix the other
way to do this computations is to
actually run simulation so you start
with a particular node in the ground and
here is our graph structure and you
literally simulate random walk so you
start here you select on every step okay
take a neighbors go here take neighbors
go here take neighbors go here all right
after three steps we ended up on this
node then run simulation again one say
two and on the three steps it came back
okay that's fine
then run simulation again say one two
three ended up on this node and just
keep running those simulations and
calculate the frequency with which the
the walk ends up on the particular node
and then estimate the probability after
n step by just counting so counting how
many times when you started random work
walk from this node it ended up on one
of its neighbors and it's not
necessarily nearest neighbor it in in
two steps and three steps now though
seems like it's much easier to multiply
matrices than doing this this has a
pretty big advantage because when you do
matrix multiplication you do global
operation you're actually doing it for
the entire graph here it's very local so
you literally if you want to detect the
cluster within the vicinity of your
cluster I well you just have to simulate
this now the authors of the paper the
original paper Poncelet happy they did
not use this idea of locality they in
fact tried to do the this hall you know
graph partitioning scheme and and they
did it in the fashion in a spirit of
hierarchical clustering so the idea was
the following
ok let's calculate similarity between
nodes
um the similarity would be computing the
same you know the way we have discussed
it will be like the random walk
similarity to render one distances and
then let's just do like you know
traditional hierarchical clustering so
this is the same way as as it's done has
been done before to do that we need to
define the descent cost our centroids
and we need to define the distance
between two clusters which is you know
again we did it previously you know you
can have a single linkage so you can you
can calculate the distance in between
the closest
items in the cluster you can calculate
the complete linkage you can calculate
work distance so they're like bunch of
distances in between clusters when you
build a hierarchical scheme and that's
what authors did and here is the
algorithm so again it starts with
assigning each verdict to its own
community it would compute distance
between adjacent vertices and distance
is this random walk distance right it's
random water distance or random walk
similarity between nodes we chose two
closest communities on every step and
more
so it is like classical hierarchical
scheme and then we update distances
between communities so you know again
recompute random walk thing and after n
minus 1 steps that the whole graph will
of course merge into one big community
so you know again it's the same the same
idea as as we talked previously with all
the sort of similarity based clustering
you know you start by merging by merging
and merging emerging merging then it all
merges together into one big cluster
here is an example again by looking at
this it's even you know hard to say how
they what metric has been used but the
idea is the following that if we you
know the node like for example 4 13 and
14 or nodes 10 11 13 and 14 if you look
at the other sort of structural
connectivity it's not clear that they're
the most closest in terms of structure
but they happen to be the closest in
terms of this diffusion structure and so
on the first step you know we merge this
two nodes this denotes this two nodes
this denotes their next step you know
you increase class size etc etc until
you know you end up with this two and
then you know the last step will be
merging them together and this is our
partition tree and then as we previously
done you you can cut it on every on any
level you want and you know get your
clusters now if we do it if you want to
build this whole tree structure and
build a clustering for all nodes in the
graph then it's better to compute the
diffusion distance through matrix
multiplication because it calculates
that distance for every nodes right away
but if you want to for example see the
structure like local structure or let's
say
local structuring here and you really
don't care about the diffusion in other
sides because you know you're looking
into local structure here it's better to
just run simulations and do random walk
like literal random walk and then just
you know calculate what's new to
calculate here so that's pretty much the
idea of this walk trap community
algorithm so the idea is merging two
things you calculate two random walk
similarity or you calculate distances
between nodes through random walk you
use them as a similarity between nodes
and and then use traditional a
hierarchical clustering to find
communities okay any questions about
this you guys still here too much or or
too easy okay all right well in fact we
have just one more algorithm and we're
done um I might have even actually have
probably started start with that it's
because there is some mathematics here
but it's you know this is probably this
this is the only algorithm out of
today's lecture that actually has theory
behind it
and you know if you're into good
mathematics I would strongly recommend
to read this paper by Dan Stillman there
is a reference at the end it's called
local clustering algorithm and it's also
very interesting because this this
algorithm came from
so then Spielman he is computer science
interpretation so it comes from computer
science science theory this algorithm is
known among computer scientists and it
has provable convergent guarantees it's
actually very good its
kind of unknown to wider community of
biologists and people who do use a lot
of clustering so a network detection
probably eventually we'll get there so
the idea here is we actually you know
calculate things we actually optimizing
things here and I want to remind you
this metric we we talked about last time
which is called conductance previously
on a previous lecture we actually use I
think we use the definition it was Q
when you split into two when you split
graph into two petitions Q V 1 V 2 we
talked about this cut we won with 2
divided by volume somehow today it
doesn't want to write so mean volume V 1
volume V 2 okay so the only difference
here is the following I'm saying okay
well let's assign this conductance value
to a verdict set s and the splitting of
the graph into two pieces and we'll talk
about two pieces would be we finding cut
in between s and V minus s so for
example here we have a set that is green
that would be our s and the blue notes
will be V minus s and we were
like to calculate the conductance and
the conductance is really the number of
edges that do cross the boundary in this
split alright so this is a cut the value
of cut so we have one two three four
five six seven edges so the value of cut
is seven and we normalize it to the
volume of s and the volume of B minus s
so to the volume of the green nodes and
the volume of the blue nodes now volume
I just want to remind you is the total
sum of degrees of the nodes of the node
degrees in that set so the total this
total sum is really the how many a just
sort of emanate from from those nodes
and you know it for example you know for
the for the blue nodes and everything
then then we do conductance we take the
minimum so for the blue nodes for the
blue nodes you can easily calculate what
we have here so um there are two right
the node degree to no degree three two
two two right so it is 2 plus 2 plus 2
plus 2 8 plus 3 11 so that's your 11 and
so the cut value is 7 11 ok 7 over 11
number I'm sorry another cut the
conductance the conductance is the ratio
of 7 to 11 the ratio of the cut to the
volume okay why do I want to bring back
this conductance well in fact it happens
that conductance have has a very very
tight connection to the random walks and
here it is let's look at
at this graph it is very clear you know
if we start a random walk let's say we
started random walk here say the random
walk in one step will not leave this
community right it will stay in that
community if we have one step ran the
walk because you know one steps in one
step we can either go here there are
your feeder here or here or here in two
steps there is a chance to leave the
community because on a second step know
that the walk is there not on one step
there is no chance now if your random
walk starts here it can leave the
community and go to the neighbor works
if it starts here and also in the
community now what the probability that
the random walk if it starts on the red
node um we'll leave this small cluster
well the probability is there you know
for the random walk there are four ways
to go so the probability that if it
starts and there's no the probability
that it will leave is really one fourth
and the probability that will stay is we
want to stay on the first step get 3/4
right because on one step you can either
be there was there are four ways to go
you know one way which is to the left
will lead to another community so the
probability to go to another cluster is
1/4 the probability to stay its report
it's just sort of August now what's
really interesting is that the
definition of of conductance is in fact
is the probability that
one-step random walk that starts
anywhere in the cluster will leave the
cluster in this one step okay again so
it is a probability that random walk
that starts somewhere in this cluster on
any of those nodes will leave the
cluster in one step that is the
conductance now why is it so well the
reason is very simple because uhm when
you think about this what's sort of
what's you know when they do random walk
what's gonna happen
well the walk should take one of the
edges the work should originate from one
of the nodes and follow one of the edges
and so let's say if walk are starts from
this node it has to follow one of these
three edges so in some sense it should
select one of those three edges if it
starts from this node it should select
one of those three edges starts from
this node yes one of those edges etc so
in fact you know random walk on the very
first step will select one of those
edges see now look the question is how
many edges will lead so how many out of
how many
starting ages it can choose well every
node contributes its degree number of
edges so the total number of edges you
can start following the sort of edge
stops is really the sum of the node
degrees in that petition
again it's not the total number of edges
in that petition in the sum of the node
degrees because we're dealing with
starting random walk from a node and
following one of the edges so it's sort
of the edge stops how many H stops every
node provides so that's so many ways to
start random walk there is 1 2 3 4 5 6 7
8 9 10 11 12 13 14 ways to do a teacher
how many of them will lead out on the
pasture or in this case only one well if
we go back here that's really the
definition of conductance this is how
many edges live from the cluster and
this is for the minimum of volume so in
this sense conductance is really the
probability that one-step random walk
and we're talking about one step meaning
you know just walking once starting
somewhere in the cluster will lead out
of the cluster and that this is a
connection between we and conductance
and random walks and so the algorithm
I'm going to talk about we're going to
explore this and idea is the following
so we select a vertex and we try to
simulate a random walk without around it
and we'll do this random walk that
happens in T steps in particular in
their paper the authors use what's
called lazy random walk which means the
following you do like a random walk
random walk step with a probability 1/2
and with the same probability you stay
on on the node so it's literally sort of
artificially adding to every node loop
that takes probability 1/2 of saying
that creates sort of lazy ran the walk
because you know if we don't have that
additional term coming too
random walk when it comes to to note um
it instantaneously have an option to
either go here there there or there um
in this case okay there is a 50% chance
that on the next step you know you
you'll stay on the same node and the 50%
chance that you will go in one of those
directions now the reason this is done
is because they really want slow random
walk slow diffusion process and then um
as always with random walk when you
start with some initial probability
distribution to calculate the
probability distribution at after a few
steps well what you do well you multiply
it by the random walk matrix in the
power of the number of steps and that
brings it to the algorithm now the
algorithm is actually a little tricky
there are quite a few parameters it
works really really well in practice and
has guaranteed convergence properties if
you're interested take a look at at the
paper by dense Killman
the idea is the following so we start we
start with some initial initialization
for distribution of the probability on
the nodes and then we iterate with this
random walk operator but the Freak is in
here so in plain English what happens is
the following um we start with a vector
that corresponds to the probability of
being on a different nodes and we do not
need to look at the entire matrix you
can just look at local neighborhood of
the node and then we
trade by taking this distribution and
multiplying by the random walk matrix
and we'll get sort of you know another
vector with probability values and then
what's going to be happening is a
following will actually cut off the
random walks that has very low
probability so if there are some values
in the distribution this is distribution
vector that are below there a particular
node degree and times epsilon so if the
probability values here P less than no
degree times some value epsilon and and
there are ways to determine this epsilon
then we just zero out let's say here and
these two guys are below we just zero
them up and then we iterate so it
creates what's called truncated random
walk so in some sense what it does is
the following that if you have a if we
have a graph structure and we start
walking on that structure from some node
and we calculate
the probability being on the neighbors
and probability being on the neighbors
after several steps if the probability
to be on some neighbor is very small
because of the structure of the graph
we'll just assign zero to that
probability
so we're truncating that walk which
means we're not gonna consider this
random walk anymore we cut it short but
say for this node since there are say
two different ways to get to that node
the probability will not be small so we
keep it and and that's a trick so you do
iterations like that truncated
iterations every time cutting out and as
a result and the result you get some
distribution and the second step in in
this calculations will be the following
you take this vector with the
distribution vector and these sort nodes
based on this ratio of the probability
being or the value in this vector two
words the degree of the node now the
reason you always sing here
normalization to the node degree is
because if you let this random walk run
forever it will converge to node degrees
and so this is like sort of the idea is
you do not let the smart of chain to
converge to stationary distribution
because stationary distribution is
proportional to not degree you cut it
short and then you're sort notes based
on the ratio of the degree of
probability being on that node to the
node degree and then you do the sweep
the same sweep idea as we did with you
guys on spectral method now you can room
you can order the nodes you can actually
sweep and calculate on every step you
can calculate the value of the cut and
when you find the cut that satisfies
your criterion you stop
so this algorithm will allow you to
start from one particular node go look
around in the neighborhood and by
selecting certain parameters cut out the
small cluster this algorithm has a bunch
of parameters it has a parameter which
which is so this epsilon it has a
parameter this value of the cut the good
news because it actually the ridic limit
is algorithm you can estimate those
values and you can take this values from
from theory and so you know what to
expect you know what what kind of
reasonable values will be there and here
is an example of this type of algorithm
it's a little bit different there is
actually PageRank involved in these
particular calculations but the idea is
very similar that you start on a
particular node and you calculate the
sort of the random walk around it is
this truncated random walk you calculate
probabilities and that will do you know
clustering for you so I think that the
the the fundamental thing here is that
you do not need to deal with the entire
graph if you want to pull out a few
clusters or in some neighborhood um you
can just do it think about it the
following way let's say you have a you
know communication network the phone
number is people calling two people
right right in order to find out
clusters within a within the customers
who live in Moscow you really don't need
the entire call graph for the entire
country so what you do is you start with
a few phone numbers in Moscow and you
calculate does the the random walk
around those numbers and and that what
sort of makes this algorithm scalable so
again the idea we talk about three
different sort of approaches we talked
about the approach top-down right when
you take you know when you have a graph
and you start partitioning it into
pieces right and that's what you do at
home and spectral I'm take the graph
split it into pieces pleated splits
believe it we talked about merging nodes
and and building hierarchy I'm down up
we talked about actually a
multi-resolution scheme where which is
very similar to this hierarchical
construction and and this is a sort of
one more approach which is local where
to calculate the clusters you do not
need the entire graph you need a seed
point around which you want to do the
clustering and and so this isn't the key
to to this algorithm now again as you
might probably have noticed the
algorithms that are heuristic they're
very very simple and very easy to
understand the algorithm that are based
on theory I'm much harder to understand
they have many more details and the more
complicated now you know why why bother
right why bother doing all this sort of
smart stuff you know if it's so harder
there are the easy things well I guess
the the wrong answer for that is this
type of algorithms that are based on
theory they have much more predictable
behavior so you know you well if it's
gonna run on some you know a particular
graph or not you know how to you know
you know how much is gonna cost you for
this algorithm to run and you and you
have estimation for the quality of the
clusters you can get from that from that
algorithm now you might say so what I
mean you know if this is complicated
algorithm I can just take simple
algorithm and just run it and who cares
and in fact lots of research done
exactly that way so you just take bunch
of very simple heuristics and run them
on the data and see if you're lucky and
get good results unless you're computer
science and and really want to you know
build predictable and better algorithms
most of the researchers in fact do use
all this heuristic ad hoc methods
but it's good to know that you know you
need it the route written with the
predictable behavior one more sort of
word of wisdom about the real-world
communities this is a great paper by
journalist colleague and kevin langan
and Kawada thora quarters about real
world networks so they studied real
world networks for four clusters and
they found that you know in many real
world networks well the way that
networks are constructed the social
networks they have a core which is a
bunch of nodes very tightly connected
and what they have bunch of smaller
groups of nodes sort of attached to that
core they call them whiskers you know we
have seen this this structure it is
actually it does repeat itself a lot in
social networks and this structure
dictates the parallel distribution and
other things well what guys noticed that
because of this structure when you try
to calculate when you try to do
community detection sometimes good
communities just do not exist so it's
very clear that this whiskers they're
good communities the cuts if we look
here and at the cuts right
at values this card this card remember
cuts is this number of edges will be
small so it'll be very good communities
but after we cut them out we're stuck
with the core and quite often there is
like up to 80% of the nodes are in this
core and there is no good partitioning
partitions in there sort of it's obvious
from this picture now the way it's you
can explore this is for example to
calculate and plot the conductance and
the conductance is what we we just did a
couple minutes ago that write the ratio
of of the cut value to the volume in the
cut versus the size of the cluster and
when we're looking for small clusters or
small clusters and this is around I
believe this is around hundred nodes so
when you're looking for small clusters
there are good small clusters in the in
in the social network but when you try
to find larger clusters you're gonna
fail because larger clusters that means
they will live somewhere within the
score and and the conductance will
actually you can see here you go and get
bigger and bigger cluster and the
conductance the cut the quality of the
cost or diminishes so you need to be
aware what you're looking for sometimes
if you want to find with large clusters
they might not just exist there and
whatever algorithm you're gonna run you
might have a very very poor conductance
value so it's worthwhile exploring that
the graph before you start cutting it
and probably you know when you have you
do have in many algorithm control of the
size of the cluster you're looking for
start with smaller cluster and increase
the size because eventually it seems
like you will hit this sort of the
bottom and then when you try to get
bigger clusters look at the quality will
diminish so that's sort of the the real
world I strongly recommend you to look
at this paper if you're interested in
clustering
so this is the summary table from 2010
over the bunch of clustering algorithms
by now there is probably three times
more algorithm than than shown here we
just touched upon if you are written
here we talked that there is this let's
have it ones algorithm there is Neumann
and gear run and again um there is gosh
there is this algorithm we talked about
today um this is mcl clustering so you
know you can look at those and and
what's good about this this this review
is it actually shows the computational
complexity of the algorithms um now you
have to be careful because there is for
example here an algorithm that we talked
about today that is exponential in n
this is overlap clustering we started
today with this it's exponential you
know in in the dense graphs right it can
actually do much much better in in
sparse graphs this is the one that that
uses maximal cliques but still I'm you
know overall when you look at this you
realize that you know if you're dealing
with big data you know for your
algorithm that are both n o M okay o log
and that's what you're looking for while
in the worst case is may be you know
sort of n log N or n log M or things
like that right and here you have n
cubed right or you know M to the fourth
and M Squared so you have to be very
careful before you actually take sir you
know the graph community or clustering
algorithm and just apply it on large
graphs you might never get your results
back and again the reason is not because
their algorithm are bad the reason is
because the problem originally isn't be
hard it's just a problem of you know
integer optimization finding groups of
nodes that can be connected to each
other they're pictorial large number of
those and that's why the algorithm in
general have very sort of bad
scalability but some of them you know
and that's why you know when somebody
says this is leaning out it's extremely
exciting and and and that's the case of
say this label propagation that is
completely a clock algorithm but it does
sort of work but it does it in linear
time and so of course you know everybody
will try that how great well that's
pretty much it here here's a bunch of
papers for today's lecture with
different algorithms um the last one is
theoretical paper and and I think I've
shown this through references before if
you're interested in community detection
question graphs these are three reviews
the latest one is 2010 so it's five
years ago has been a lot of things since
then but um as far as I know there was
has been no sort of updated review out
there so lots of work on on community to
actually happened in you know 2000 2010
okay any questions you guys don't look
while the good news we're done with this
module I'm not sure if it's a good news
or bad news but we'll have another
marginal of of algorithms so what have
we done in this module just this is a
very quick summary so first of all we
talked about
we started with talking about network
characteristics we talked about power
law degree distribution we talked about
small damage or damage of the network we
talked about high clustering coefficient
there so three major features for the
network we then talked about network
models we would consider three network
models random graph preferential
attachment and small world model we then
spend a lecture on centrality measures
and and talked about various measures of
the centrality on importance of the
nodes it was degree closings in between
the centrality we talked about elite
analysis and how to actually take into
account the connectivity and did the
PageRank and its algorithm both of those
take the connectivity of the entire
graph into account when the computing
the ring for the nodes we then talked
about equivalence for the different
nodes in the graph vertex or node
equivalence and the idea of similarity
how similar nodes are based on the
structure we discussed restorative
mixing which is idea that similar nodes
connects to similar and and you know we
talked about similarity based on the
node degree and and based on labels we
briefly touched on network structures
things like cliques scores and we spend
quite a lot of time on on network
communities and and in fact this is one
of the most sort of computational
challenging problem in in networks these
days so we talked about similarity
clustering we talked about graph
partitioning we talked about overlapping
communities and today we spent time
doing eristic s-- and all kind of friend
of walking
this is pretty much the sort of the what
we did in this module we will talk a
little bit more about the final project
and Andre will give you a little bit
more precise instructions on what we're
expecting from you in an analysis of
your Facebook network and next module
will be actually devoted to dynamical
dynamics on graphs so we'll talk about
various processes on graphs like
diffusion rumor propagation epidemics
we'll talk about evolution of graphs so
how know how edges appear disappear and
and we'll talk it will do a bit of
machine learning on graphs will do
predictive modeling on say the
prediction of connectivity patterns and
the prediction of edges in the graph so
that's the plan that's it for today do
we have any questions