1
00:00:00,480 --> 00:00:04,660
So, what are we going to do next is to
take our affiliation graph model and

2
00:00:04,660 --> 00:00:07,960
simplify into something
that we will call BIGCLAM,

3
00:00:07,960 --> 00:00:11,900
which will allow us to detect
communities in large networks.

4
00:00:11,900 --> 00:00:13,330
So, let's see how we do this.

5
00:00:14,430 --> 00:00:19,640
So the previous case, what was kind
of problematic, in terms of trying to

6
00:00:19,640 --> 00:00:25,210
fit the model to the data, is that we had
this big, bulky, bipartite structure that,

7
00:00:25,210 --> 00:00:29,080
that we have to fit and basically
search over this affiliation graph.

8
00:00:29,080 --> 00:00:33,060
So what we will do now is basically
relax the, the model a bit.

9
00:00:33,060 --> 00:00:35,700
And the idea now is to say,
rather than, than for

10
00:00:35,700 --> 00:00:38,820
every node to have a 0-1
type of membership,

11
00:00:38,820 --> 00:00:42,920
in a sense that I can either be a member
of a given community or a non-member.

12
00:00:42,920 --> 00:00:48,280
Now we want to actually model the strands
of every node community membership.

13
00:00:48,280 --> 00:00:53,500
So the idea will be that we will have this
non-negative strand of every node being

14
00:00:53,500 --> 00:00:55,190
a member of a given community.

15
00:00:55,190 --> 00:00:57,290
Of course, if a strand of membership is 0,

16
00:00:57,290 --> 00:00:59,880
this means a node is not
member of the community.

17
00:00:59,880 --> 00:01:03,960
And if the strand of a membership is very
high, this means that the node is very,

18
00:01:03,960 --> 00:01:08,300
kind of, active part or
an active member of a given community.

19
00:01:08,300 --> 00:01:13,850
The way we will think of these strands,
we will, we will label them as Fu comma A,

20
00:01:13,850 --> 00:01:17,620
where u is the name of the node and
A is the name of the community.

21
00:01:17,620 --> 00:01:21,830
So we will call this membership strands F.

22
00:01:21,830 --> 00:01:23,330
And they are non-negative values.

23
00:01:23,330 --> 00:01:26,670
So basically, 0 means no membership and
anything greater than 0 means

24
00:01:26,670 --> 00:01:29,940
that you are a member of a given
community, to a given degree.

25
00:01:29,940 --> 00:01:31,600
So now the question is,

26
00:01:31,600 --> 00:01:36,790
how do we think about links of
the network arise from this model?

27
00:01:36,790 --> 00:01:39,080
And the way we will think about
this is very similar to what we

28
00:01:39,080 --> 00:01:39,930
have been doing so far.

29
00:01:39,930 --> 00:01:44,430
So we will say that each community
A links nodes independently.

30
00:01:44,430 --> 00:01:48,020
And the probability that two nodes
are linked due to a given community,

31
00:01:48,020 --> 00:01:50,530
meaning them being a member
of a given community,

32
00:01:50,530 --> 00:01:55,670
is simply 1 minus the exponential
of minus product of

33
00:01:55,670 --> 00:02:00,580
the membership strands of the two,
of the two nodes in that given community.

34
00:02:00,580 --> 00:02:03,020
So the idea is very simple, right?

35
00:02:03,020 --> 00:02:07,163
If we are are both members to that
community to a very high degree,

36
00:02:07,163 --> 00:02:10,020
then our product will be large.

37
00:02:10,020 --> 00:02:11,150
We have a minus sign here,

38
00:02:11,150 --> 00:02:16,280
so exponential of a very large negative
number is something very small.

39
00:02:16,280 --> 00:02:20,262
So the communi,
the total probability will be high.

40
00:02:20,262 --> 00:02:24,491
For example, what is also a nice property
of the product is if node v is, for

41
00:02:24,491 --> 00:02:27,963
example, not a member of a given
community and node u is a member,

42
00:02:27,963 --> 00:02:31,879
is a member of that community,
then it will be 0 times something else, so

43
00:02:31,879 --> 00:02:34,560
the whole thing will be 0.

44
00:02:34,560 --> 00:02:35,820
That is also nice.

45
00:02:35,820 --> 00:02:39,480
And then, another thing is,
if we have nodes that are members to

46
00:02:39,480 --> 00:02:43,890
a given community to varying degrees,
we will take the product of the two

47
00:02:43,890 --> 00:02:48,760
corresponding strands to compute
the overall linking probability.

48
00:02:48,760 --> 00:02:53,860
So now, this is the idea of,
of having a linking probability for

49
00:02:53,860 --> 00:02:56,720
nodes u and v,
belonging to a single community A.

50
00:02:56,720 --> 00:03:00,860
So now, what happens if nodes
share multiple communities?

51
00:03:00,860 --> 00:03:03,940
In order to achieve this,
we have to first define what we

52
00:03:03,940 --> 00:03:07,420
will call the community
membership strength matrix F.

53
00:03:07,420 --> 00:03:12,196
So, here is my matrix F, and let me
tell you what, what its.structure is.

54
00:03:12,196 --> 00:03:14,445
So this matrix F has
the number of columns,

55
00:03:14,445 --> 00:03:17,320
which is the number of
communities in our network, and

56
00:03:17,320 --> 00:03:21,740
the number of rows of this matrix equals
to the number of nodes of the network.

57
00:03:21,740 --> 00:03:26,350
And every entry of this matrix tells
us to what degree does a given node,

58
00:03:26,350 --> 00:03:31,830
in a given row x, belong to a given
community in a given column, okay?

59
00:03:31,830 --> 00:03:36,580
So the, what we can then do is, if you
think of a single row basically being

60
00:03:36,580 --> 00:03:40,980
a description of what, of what the,
what are the communities a given node is

61
00:03:40,980 --> 00:03:46,580
member of and to what strength is, is
given node, the member of that community.

62
00:03:46,580 --> 00:03:49,780
We can basically think that this
completely specifies the community

63
00:03:49,780 --> 00:03:51,180
structure of our network, right?

64
00:03:51,180 --> 00:03:54,430
For every node,
we know what communities it belongs to.

65
00:03:54,430 --> 00:03:57,310
And we can think now of every,
every row in this case

66
00:03:57,310 --> 00:04:01,650
as a simple vector of community
membership strands for that node.

67
00:04:01,650 --> 00:04:05,290
So as we have discussed,
now the question is,

68
00:04:05,290 --> 00:04:08,530
how do we compute the probability
of our connection?

69
00:04:08,530 --> 00:04:12,820
The way we compute the probability of
a connection is simply probability that is

70
00:04:12,820 --> 00:04:15,980
proportional to the product of
the strengths of the two nodes.

71
00:04:15,980 --> 00:04:18,260
So we, we have already seen the equation.

72
00:04:18,260 --> 00:04:21,210
It is simply probability of our
pair of nodes being connected,

73
00:04:21,210 --> 00:04:26,500
due to our given community A, to be 1
minus the exponential of minus the product

74
00:04:26,500 --> 00:04:31,580
of the strands of the committee membership
of nodes u and v to a given community A.

75
00:04:32,660 --> 00:04:36,350
So now that we know how likely is a pair
of nodes being connected due to our

76
00:04:36,350 --> 00:04:40,492
membership to a given community A,
now we want to generalize this and

77
00:04:40,492 --> 00:04:43,550
say, what if a pair of nodes has
multiple communities in common?

78
00:04:43,550 --> 00:04:46,585
And we will use the same approach as
we did with affiliation graph model,

79
00:04:46,585 --> 00:04:50,600
we'll say the probability of a pair
of nodes being connected is propor,

80
00:04:50,600 --> 00:04:53,590
is proportional to the,
to the idea that at least one of

81
00:04:53,590 --> 00:04:56,010
the communities they have
in common created an edge.

82
00:04:56,010 --> 00:05:01,400
So, here it is, the probability of pair of
nodes being connected is simply 1 minus

83
00:05:01,400 --> 00:05:06,280
the product over the communities, 1 minus
the probability of them being connected,

84
00:05:06,280 --> 00:05:09,272
given that they share a membership
in a given community.

85
00:05:09,272 --> 00:05:11,540
So this, this formula simply says,

86
00:05:11,540 --> 00:05:15,690
what's the probability that at least one
of the communities creates a connection.

87
00:05:15,690 --> 00:05:18,990
So, what we want to do now is think
about this formula a bit more and

88
00:05:18,990 --> 00:05:20,320
actually try to simplify it.

89
00:05:20,320 --> 00:05:23,630
So let me show you how we
can simplify it further.

90
00:05:23,630 --> 00:05:29,160
What we have so far is to say, given
community A, here is the probability that

91
00:05:29,160 --> 00:05:32,500
a pair of nodes is connected,
due to the membership to that community.

92
00:05:32,500 --> 00:05:34,020
Then we said, we said, right?

93
00:05:34,020 --> 00:05:38,076
The probability of nodes being connected
in the network is proportionate to

94
00:05:38,076 --> 00:05:41,938
the probability that at least one
common community that they have in co,

95
00:05:41,938 --> 00:05:45,320
that a pair of nodes has in
common links that given pair.

96
00:05:45,320 --> 00:05:47,950
So, I have the expression
from the previous slide,

97
00:05:47,950 --> 00:05:50,860
now let's try to simplify things a bit,
right?

98
00:05:50,860 --> 00:05:55,500
So, the first thing I can do when I
have this value P sub c, I go and, and

99
00:05:55,500 --> 00:06:01,630
insert and insert our expression for
the probability of an edge.

100
00:06:01,630 --> 00:06:06,560
And now, what I notice is that the first
line 1 and the second 1 will cancel out,

101
00:06:06,560 --> 00:06:12,110
so all I will be left with is a product or
the expo, exponentials and

102
00:06:12,110 --> 00:06:15,450
then a product of
the membership strengths.

103
00:06:15,450 --> 00:06:20,230
A product of the exponentials is some
of the things in the exponent, so

104
00:06:20,230 --> 00:06:26,850
I can, I can simplify this simply to say
this is 1 minus exponential function.

105
00:06:26,850 --> 00:06:31,180
And then sum over the communities,
product of the corresponding strands, and

106
00:06:31,180 --> 00:06:33,030
then I have this minus here.

107
00:06:33,030 --> 00:06:35,460
Now, what we notice is that the, the,

108
00:06:35,460 --> 00:06:39,260
the summation that we have here
is simply a dot product, right?

109
00:06:39,260 --> 00:06:40,560
It's a, we are going and

110
00:06:40,560 --> 00:06:44,090
multiplying the components of the two
memberships' transvectors together.

111
00:06:44,090 --> 00:06:46,766
So to write this more compactly,
here's the expression.

112
00:06:46,766 --> 00:06:52,770
We say that the probability of node
u linking to node v is simply 1 minus

113
00:06:52,770 --> 00:06:58,490
the exponential of minus, and
then it's a dot product of factor that,

114
00:06:58,490 --> 00:07:04,590
basically a row, for the node u and
a row for node v, right?

115
00:07:04,590 --> 00:07:07,420
Where these rows basically tell us how,

116
00:07:07,420 --> 00:07:11,480
to what degree is a given node
member of a given community.

117
00:07:11,480 --> 00:07:15,800
So, to give you an example,
here I can think of my ma, my matrix F,

118
00:07:15,800 --> 00:07:21,056
where I have the factor vectors of the
community strengths membership vectors for

119
00:07:21,056 --> 00:07:22,410
the three nodes.

120
00:07:22,410 --> 00:07:23,690
So now I can start asking,

121
00:07:23,690 --> 00:07:26,410
what is the probability of a given
pair of nodes being connected?

122
00:07:26,410 --> 00:07:29,490
So, for example, I can compute,
given the formula above,

123
00:07:29,490 --> 00:07:33,970
the probability of nodes u and
v being connected, that is very simple.

124
00:07:33,970 --> 00:07:39,440
It is 1 minus the, the e to the,
raised to the power of minus 0.16.

125
00:07:39,440 --> 00:07:44,840
If I do that, the value is 0.14, so this
is for nodes u and v being connected here.

126
00:07:44,840 --> 00:07:48,760
What we see is that they, they have
the only reason they, they can be

127
00:07:48,760 --> 00:07:52,040
connected is because they share
the membership of the fourth community.

128
00:07:52,040 --> 00:07:55,520
I can, for example, ask,
what is the probability of nodes u and

129
00:07:55,520 --> 00:07:56,390
w being connected?

130
00:07:56,390 --> 00:07:59,050
Here is node u, here is node w.

131
00:07:59,050 --> 00:08:02,840
What we notice is that they
have one community in common,

132
00:08:02,840 --> 00:08:03,990
the same as in first case.

133
00:08:03,990 --> 00:08:08,910
But now, they both are very strong, have
very strong membership to that community.

134
00:08:08,910 --> 00:08:12,680
So the overall linking probability that
we compute out of this is very high.

135
00:08:12,680 --> 00:08:17,550
But for example, nodes v and
w have the linking probability of 0.

136
00:08:17,550 --> 00:08:18,380
Why is that?

137
00:08:18,380 --> 00:08:21,620
Is because v and
w have no common communities, right?

138
00:08:21,620 --> 00:08:26,440
In the first case,
one is a member of the first community and

139
00:08:26,440 --> 00:08:29,640
the second node is not, and
so on and so forth, right?

140
00:08:29,640 --> 00:08:32,660
So, what do we,
what do we see from this is that kind of

141
00:08:32,660 --> 00:08:35,910
the model has exactly
the components we would like.

142
00:08:35,910 --> 00:08:39,570
If nodes are members to a given
community with very high strength,

143
00:08:39,570 --> 00:08:40,950
the probability is large.

144
00:08:40,950 --> 00:08:44,971
If the strength is low, the linking
probability is correspondingly small.