so the topic of today's lecture is
introduction to network size so I'm
going to talk about plans for this
module and we'll do some introductory
I'll talk about some introductory
material so first of all if you class
technicalities my name is Lena Jo cough
and the TA for the class will be
ungracious knockoff
the course will consist of two modules
and each module will have ten lectures
and ten labs and Andre will be taking
care of labs so far the schedule is of
lectures we'll have a Thursday from 6 10
p.m. until 9 p.m. I'll hear the website
where you find all the information about
the lectures um the rest
there are also material there are papers
available there and you will also um the
homeworks will be posted there my emails
is LG gov at HS here are you and Andres
emails also given in terms of
programming will be using Python and in
particularly using ipython notebook and
we'll be using Network X as main on
library well in fact you could possibly
code a lot of things yourself but for
efficiency reasons we decided to stick
with Network X and for some large
networks it will be good to use external
software to visualize them and we could
use we'll use either Getty or ye D
resolution software finally most of the
lectures will be online and we'll be
using zoom meeting software so what are
the prerequisites for this course well
first of all it's discrete mathematics
it's linear algebra um I'll go to data
structures it would be good if you have
some probability theory or differential
equations
and we do require skills programming in
Python we will not teach that though
we'll have some introductory material
for ipython if you never use them from
leading algebra I will require some
basic knowledge which are vectors and
matrices operations on vectors and
matrices it would be good to know about
sparse matrices and the type of storage
used for sparse matrices
and finally eigenvalues and eigenvectors
now eigenvalues and eigenvectors will
use a lot and if you don't remember what
that means or how to find them please
look it up from graph theory we'll need
some main concepts so what graph is
we'll talk about various types of graphs
which directed undirected simple graph
weighted graph you will need to know
what connected and strongly connected
component of the graph are no talk about
paths and cycles in the graph I will
talk about shortest path about trees so
these are all sort of main fundamental
concept that you learn in discrete
mathematics and in the algorithm class
there are several algorithms that are
also critical for us it's breadth-first
search depth first search algorithm
algorithm for finding connected
components and shortest paths again if
you don't remember them please check
them out in terms of textbooks well
though right now there are several very
good books out there
first of all we'll be using a lot of
market humans um introduction networks
introduction book there is a very
interesting book on networks crowds and
markets though this that book is
probably more oriented more towards
social science scientists and I did less
strict in term of mathematics used in
there I'm very very interesting book on
social economic networks by Matthew
Jackson and there is there is absolute
classics by Stanley pastor Martin
Katherine files and social network
analysis what I will provide right
to certain chapters in that book and
there is a very nice book on network
analysis and the methodological
foundation this is actually collection
of articles but they are these articles
are on the surf under mental aspects of
computations with networks there are
also several very very good and detailed
reviews
the first one is reviewed by algorithm
barabash i'm statistical mechanics
complex networks it's well it's it's
pretty dated for right now but it's
probably still one of the sort of the
best and the biggest reviews
um the alternative is review by Mark
Newman structure and function of complex
networks so links to those are available
on the class website so what we're going
to do this module will have ten lectures
and here's a plan will do introduction
to network science today and we'll talk
about the problems network science deals
with and some major properties of
complex networks next lecture will be
devoted to power laws and will talk
about all the power all kind of power
laws and their role in in in network
theory third lecture will be about
random graphs and ran the air - Ronnie
models a friend of ground generation the
first lecture is about small world and
dynamical growth model these are new
models that that scientists came up with
10 15 years ago and then we'll switch a
little bit and talk about some metrics
and measures on the graph and first of
all we'll talk about centrality measures
and the notion of not centrality and
importance of the nodes and ranking of
the nodes and we'll talk about link
analysis or how what role links play in
in in centrality in the node centrality
and we'll discuss here PageRank and hits
and other modern algorithms for web crap
graph analysis
lecture number seven will be about
structural equivalence or about finding
similar nodes in the network single in
the sense of the roles and so between
its connections and the network and then
we'll spend the last three lectures on
network communities we'll talk about the
definition of various definition of the
communities will talk about algorithm
that allows us to detect communities
will talk about graph partitioning as a
way to find community the network and
we'll talk about specifically design for
community detection algorithm
pacifically designed for that so that's
a short plan for this module of module 4
will be devoted to processes on networks
diffusion etc etc this module we will
mostly dedicate to analysis of the
structure of the network
so Network science is is a very new
science um it's actually probably you
know if you start looking for referrals
um you will not find things earlier with
the name network science you only see
such things
you will not find things earlier than
year round you know mm or late nineties
but in fact network science is formed
from various well established Sciences
so first of all it's sociology and
sociologists they used to do social
network analysis or SMA in short for
quite a long time actually in fact since
nineteen thirty's um though the networks
they dealt with we're pretty small right
it's the network that you can get from
from collecting data by hands really
mathematicians they did talk about
graphs for several centuries and in fact
mathematics there has been a
breakthrough and pretty much new field
appeared in in 50s and 60s with a
dictionary introducing random graph
theory computer scientists computer
science has been dealing with graphs a
lot crafted a data structure and
developing algorithm for shortest paths
where it shows path algorithm and other
algorithm flow methods statistical
physicist they kind of jumped on this
wagon and the late 90s with notion of
complex networks and networks being part
of the complex systems and physicists
study complex systems or complicated
wealth interact or interacting systems
with the complete complex interacting
pattern patterns
economists also talked about networks
and a lot of pairwise interaction and
there is finally biologists its
bioinformatics it's about interaction
between protein protein interaction and
many other things so
as you notice these are very very
different Sciences and each of them
bringing its own approach and a some set
they're complementary but sometimes a
little bit contradictory in the sense
that we'll see a some terminology that
is different and it really depends on
where they came from
methods and definitions an algorithm
will be different whether it came from
say biologists economists or computer
scientists or mathematicians and you
will feel that that that slight
difference so the difficulty of this
course is to put all this knowledge
together and make it usable for with
whatever it vacations you have in mind
so first of all as I mentioned I'm
terminology saying well as you have seen
on the radio I've been already using the
words network and graph well in fact
it's the same in network and graph it's
a set of nodes or vertices collected by
links or edges right so network is is
the same as graph and and when we talk
about nodes very often I will use the
term vertices or nodes interchangeably
but let's see if you look at the social
sciences literature most likely will be
about actors links edges again well
social sciences will come up relations
you will talk about communities or
network communities or network clusters
so all this different to know all the
different terminologies well eventually
or you will have your hands on it
so if you look at this picture you'll
see here separate nodes or vertices or
actors and they're connected by ages
so what's you know complex network well
again first of all network is is a graph
and so it's a collection set of notes
collected by HS we'll talk a lot about
what it means for network to be a
complex network but just sort of a few
ideas by looking at this picture you
realize that on one hand this network is
not regular not regular in a sense you
know every node has a different number
of neighbors has different connectivity
patterns but at the same times it's not
random you can see that there is is
there is some some structure in this
network for example you realize that
there is something similar sort of at
the hands here right and whatever in in
the center looks different so there is a
structure but it's not a regular
structure in a topology or the connect
the pattern of the connections is very
non-trivial
now this networks have very very very
specific properties it's called what's
called scale free networks and we'll
talk about it on in the next few minutes
but what's amazing that doesn't matter
where this networks come from Social
Sciences or from transportation or
economics or it's even brain networks
they have a lot of universal properties
which means they they're very similar
and that's that's amazing and they
describe a it's a complex system in a
sense that first of all there are there
are complicated patterns of pairwise
interactions and and the other important
property that you really need to study
them the network as a whole if you
decompose it into pieces well you'll
lose the whole thing because network is
about connection between nodes and you
know if you cut it into nodes and edges
you lose everything and this is in fact
what complex what physics of complex
system status it is that
in general an odd decomposition into
pieces so here in fewer examples here is
the Internet wonderful picture from 2003
it's an Internet traffic routing but
where every node is is a router on the
Internet and M edges are connections
they're actually quite a few connections
this picture well in fact a
visualization of networks it is a
science by itself and though there are
still there are a lot of algorithm that
allows us to visualize networks it's
actually very hard to build meaningful
picture and though this for example
picture is extremely beautiful it's not
quite clear how to actually use it
except for showing that that the
Internet is a is very very complex
object I'm not sure if we can extract
any more information just from looking
at this picture another example this is
a blogosphere there are blogs every node
here is a blog red nodes red colored red
a conservative blogs blue a liberal and
there are links between them red links
are between links from conservative blog
to conserve your blog blue from liberal
to liberal and orange and purple are
links in between them if you don't so
here is it's in a very center right
there on their own orange and purple
lengths so for example this picture you
can click though it's also looks like a
mess but you can clearly see this
polarization of political blogs you see
two clusters of two communities liberal
community and conservative community and
the communities citing each other a lot
right referring to each other a lot
here's another example from social
sciences this is a Twitter and this is
what's called hashtag diffusion well if
you use Twitter you know what it is and
well hashtag is just the way to
reference particular topic and you when
you use Twitter you can either retweet
somebody's tweet or use mansion and and
here is a propagation of particular
hashtag while in English from this paper
it's us a hashtag how it was retweeted
and you realize that there are some
people who actually retweet to a lot of
other people right and some people has
very very small difference um here is
not a very interesting example this
example where the nodes are financial
institution and do a lot of sort of
banks that you of course recognized you
know here's your goldman sachs here's
you merrill lynch and its fidelity
management and it's bark lies so let
cetera et cetera et cetera and the
reconnections between them and this and
connection mean um sort of landing or
borrowing money and you realize that the
financial structure is very convoluted
and pretty much you're looking at this
beings are all interconnected so you
know from the point of view of network
analysis might be interesting to find
out okay well what's a stability of the
system what happens if say one of the
banks goes bankrupt or we should those
banks are central or important to this
here's not a great picture of the
civilization well this is like actual
map of the republic transportation again
here nodes will be a stations and edges
will be connections between those
stations stations i believe there is all
kind of means of transportation shown
here
what makes this graph a little bit
different from what we have seen before
is the fact that it can have parallel
edges so there are some edges well if
you think about edges as a means pertain
that you'll still have some of the
running in parallel right in between
stations so there is like parallel edges
in there here is another example now
from biology this our project running
interaction network in East again you're
you sort of realize that that on one
hand the the structure here is
really not regular at the same time not
very random organizational networks this
is just a structure of some fictional
organization how people interact in that
organization on various business
purposes and finally a beautiful
pictures on a Facebook communities here
are different colors corresponds to
different communities signalization done
with Getty and say this is like the one
with probably the most famous
visualization on the Facebook of the
friendship graph of five hundred million
people just showing how you know world
is interconnected so it's in all those
examples and I promise that there were a
lot of things that are common in between
those networks so there are several
features I would like to talk about
today so first of all these all of these
networks are so-called parallel networks
or in other words they have power low
node or vertex degree distribution in
other word for that is a scale-free
network so we'll talk about it today
what exactly that means another property
is a small diameter or average path
lengths on this network the fact that
these are small world networks and the
third property is the fact that this
network has have very high clustering
coefficients or what's called
transitivity or in other words a number
of triangles so they're very very much
triangulated so these are three
properties that are very much
characteristic for complex networks
pretty much most of the networks that
occur in nature and those that we're
going to study whether social political
biological technology for networks they
will all have all have this properties
so what's power law again we'll have
entire lecture devoted to it but to give
you an idea let's take a look at this
network this is a history of the loss of
the network where different philosophers
are connected if one of the philosophers
follows their theory of another and and
if you notice if you look closer in this
picture you realize well yes oh and and
the number of the size of the node here
every node is a philosopher and the size
of the node is really just the number of
connections or pretty much the number of
the students for the philosopher the
followers of that philosopher and if you
realize they're not that many of those
big big philosophers right the residual
Aristotle let's haggle email can't
amazingly Karl Marx Friedrich Nietzsche
right and then there are smaller the
that is little it's also not big ones
and there are more of smaller
philosophers now the characteristic here
in this picture is that there are very
few but very large philosophers and
there are lots and lots and lots of
small philosophers so there is very very
uneven distribution of the number of
followers for philosophers here is not a
zoom in you'll see a here Aristotle and
you'll see Plateau and there was like
lots and lots of smaller philosophers
well we don't even have names here for
that
so what does this no degree distribution
mean in a scale for any math Network
well that is a following let's just
calculate number of links a number of
friends every node has and just count
how many of those nodes are in the
network so here um we'll have
number will show number of nodes in the
network and on the horizontal axis will
be that connectivity so how many links
they have and so here we'll have you
know one hundreds thousands of links
lots and lots of links but they'll be
very few those at the same time in a
graph will have a lots and lots of nodes
with few links with a small number of
links so that will create a very very
uneven histogram or distribution and
it's called power law distribution we'll
talk about it more on the next lecture
if we compare that distribution to the
distribution we would expect to have
from random process see that's what's
shown on the left side we'll realize
that it is very very different so in a
typical process you will have lots of
lots of nodes was approximately the same
number of neighbors and you will have
you know some you have some distribution
bell-shaped distribution with
exponentially small number of nodes with
a large number of neighbors and small
number of neighbors
so in some sense say the heights of the
pip of people um in the world
distributed according to um this bell
curve distribution which is you know
have every tried and they're people who
are a little bit taller and people a
little bit shorter if a human race under
the height of human race were
distributed according to power law then
would have very few but would have
people of half of heights you know 10
meters 20 meters etc and very very and
lots of very short people so which is
not true so for example human eyes
distributed according to bell curve but
a number of friends in the network is
distributed according to power law there
are people that have lots and lots and
lots of friends and
here on this edge of the distribution
but they're not that many of those think
about them as celebrities it have who
they might have lots of friends and lots
and lots of followers but majority of
the people are actually on this end of
the spectrum this end of the histogram
there are a lot of those people the
favorite typical people they have very
few friends um so that's called power
law this particular type of the
distribution with number of friends a
number of connections links per node
clustering as I mentioned cluster that Y
of clustering high clustering or or
transitivity it really means that if we
talk about social networks that if you
have two friends what does probability
that they know each other and we know
that in social settings if the
probability is very very high so it is
very high because of many reasons
because you know you usually meet new
people through your friends because you
need to people through your friends um
and because uh you know it's it's
it's much easier for people to get to
get introduced that way so if we look at
this graph for example at this geometric
graph now this graph is by the way is
not a social network this is just for an
example I showed geometric graph which
is generated by randomly putting points
on a plane and connecting them in
certain fashion but I just wanted to
show to emphasize that in this graph
there are lots of triangles right and so
because of that the clustering
coefficient or the transitivity of the
network is high and the transitivity is
just the ratio of number of triangles to
the total possible number of triangles
in the network and here is actual Quatro
Network which is a social graph
friendship network where people are
connected if they write papers together
and if you look you know at this graph
you realize that you still seeing lots
and lots of triangles all right they're
triangles everywhere so it happens that
a lot of social networks and in general
and complex networks will have pretty
high clustering coefficient they'll have
a lot of triangles in them and final
property which is a small world
he has another name which is called six
degrees of separation you probably heard
this phrase and it really means that I
need two people on average separated by
no more than you know several
connections in fact this idea where the
very first time was proposed by bridges
green tea it's Hungarian author in his
short story in 1929 but it came back
into sort of you know people's opinion
in John Legere plane which is called six
degrees of separation and the movie
later on though among scientists this
idea
had wrong social scientists that the
world is pretty small but circulating
since late 60s and in fact there is a
very famous famous now famous small
world experiment done by social
psychologist Stanley Milgram in 1967 his
paper shown here it's actually is called
titled experimental study of small world
problem and so here is idea of um of the
study
Milgram recruited volunteers through the
newspaper and asked them to participate
and send them out the following
instruction for the participation in
this study so that it was to actually to
be able to send a postcard from a person
from the senate-passed car to person
that is in another located somewhere far
away and particularly in his case he was
doing experiments sending postcards from
Nebraska to Boston but the goal was to
actually send a postcard through the
friends if you do not know by name there
their ad receipt of this card so here is
here is a simple here's instruction that
were given to the participant of that
experiment if you know the target person
on a personal basis so you know him mail
of the the card the fold is directly
looking but if you do not know do not
contact him directly instead mail this
folder to a person who you think might
know him so the idea was to try to
figure out if we really have a small
world if we really can pass a message
across this world and just try to count
how many steps it's going to take for
this letters folders to actually find at
receipt
here is a set up of experiment they had
recruited 196 volunteers in in Nebraska
and 100 people in Boston and the target
person was actually in Boston and so so
this is a target area over there
Massachusetts Boston and the goal of the
experiment was to actually see how many
steps it would take for the message to
get from Nebraska to Boston if it is the
letter is sent only two people that know
each other on a personal on the
first-name basis
and you know before the experiment that
the answer is we're very very different
I'm a lot of people assume that it
probably taking 100 steps and the letter
will never make it through now um the
experiment was quite tricky
um because they tried to measure several
things so they wanted to measure not
only the dread the the the path through
which things go but they want to
actually experiment with different
channels channels in the sense that they
provide not only on the name of the
person who is at receive but also his
profession and and so in some sense you
know you can if you think about how you
would locate a person somewhere you can
go through you know several channels you
can think of finding someone who are
born in the same town in this person or
finding someone who lives in the same
town or maybe it's finding somewhere
someone who has the same profession and
so we might have you know different
channels based on professions or based
on their place of birth or etc and to
make it the clinic experiments they also
looked into I'm sending this letters
also from Boston so it goes from Boston
to Boston but just to make sure you know
that if that works compare the length
the
all this intermediate steps the letter
is going to take so the information that
was given was a target name to the dress
Occupational employment college hometown
I hear the results
amazingly sixty-four letters or you know
almost 30% reached the target here's a
picture that the diagram histogram
actually showing the number of chains or
number of those um the number of the
chains of particular length so if you
look at this um you realize that here is
how many there was like around and what
seven chains of length five so it went
through five people there were fourteen
chains of length four
alright and there are probably 16 chains
of length 6 so average chain length was
5.2 now if you notice this this you know
the distribution we'll call it by model
these days right so it has two pigs and
the reason is because it happens that
the letters you could classify the
letters as going through two different
channels so one of them went through the
channel through the sort of hometown
channel so where people try to send the
letter I mean through the people who
might you know leave the bornus in town
and business contacts went through the
sort of business contacts chain it's
interestingly it's interesting to see
that a business conduct chain business
world
happen to be smaller alright and of
course from Boston it would be it was
shorter but still it took on this six
you know on an average actually on
average five point two steps five points
two intermediates to deliver the letter
which is amazing because people assume
that it might taking hundreds of people
to be able to reach this unknown person
so there was an experiment that proved
that we're actually living
a small world on that you know there's
this notion of six handshakes that that
separates people is on an average it is
more or less a reality um of course this
experiment I mean you know with when was
the development of the internet people
wanted to repeat this experiment and
most Watson reproduces experiment in
2001 by sending 48 thousand letters
email letters asking to forward email to
some person was pretty much the same
setup as Stanley Milgram experiment and
he calculated that on average it took
six forwarding to get the email to the
right person now interestingly here the
response rate of course much lower I
mean I can imagine you know if you get
email asking you to please forward it to
a friend's so who might know somebody in
Boston well it most likely to go to Jack
right but um in 2001 there was still
people who actually participated in this
experiment again this was repeated here
by Judas Kovac on Microsoft messenger
graph with 240 million users and they
got I'm averaged an average diameter of
the graph or average length of the graph
is six point six and finally it was
reproduced by Lars Backstrom at Facebook
with even more users and they actually
found out that Facebook um is much even
even more smaller world than expected so
it's only pork four point seven steps
away and if you realize if you look at
this you can also clearly see that it is
shrinking it's especially seen well seen
on on a graph for the United State users
right so the maximum is shifting to the
left so the world is getting the
Facebook world is getting smaller it's
of the true
for the entire world it's just not that
clearly seen here but um with time and
and the density of the friendship and
the Facebook increases and I'm average
Jam average path length is getting
smaller so it is a small world after all
now um if you have not thought about it
before
it might count it might sound weird now
how is this millions millions of people
it takes on these six steps to reach a
you know every person in this world well
here is a sort of idealistic a very very
naive model very simple but it can give
you an idea why this might work now
we're going to make very significant and
you know very wrong assumption will
assume that the friends that you have do
not know each other right now in fact
they do but for a second let's just
let's just assume that they do not and
see what happens let's look at this
graph let's say this is you and you have
four friends okay so you have four
connections in each of those friends
have four friends more for four more
friends um except for you
so in fact from the graph point of view
then this node degree is five but um so
there are this four extra for us here
and each of them has four more friends
etcetera etcetera etcetera so you have
four friends each of your four friends
has four friends
that means on this two-step distance we
already have 16 nodes and one on a three
steps we have 64 nodes so if you have if
a person has Z friends on average and
then let's say okay Z to the power of
steps will give us the total number of
people that the that will be connected
in the world after these steps
well if Z to the power D is equal to n
then D is is log n divided by log Z and
logarithm is an amazing function if you
take n to be six point seven billion you
know that the earth population and let's
say an average on every person has 50
friends then in fact D will be five
point a yeah so it is six with this
assumptions now you know if you have not
50 friends but hundred friends will be
the less if you have less friends it'll
do it more and of course you know we
made a very very strong and very wrong
assumption that these people do not know
that your friends not know each other
and so these are different people and so
that your network connectivity look the
connectivity grow through extremely fast
exponentially fast but still it gives
you an idea that you know if you have
that many people in each of those of
your friends that many friends and each
of your friends have as many friends
that your friends have that many friends
that in only like in six steps you
literally cover all the entire
population of the world so it's really
about the structure of the network if we
leave not in this type of world but in
the world where you know that is
dominated by regular graphs let's say
you know the friendship structure would
look like that with a regular lattice
than than the average path in between
you know
the average path lengths on this thing
will be proportional to C square root of
n if we're talking about two-dimensional
world and was well with 6 billion
billions you know it will tend to the 10
so it's 10 to the big to do a huge and
it is not so our world is really
structured out friendship and
connectivity patterns are really much
more of have more of this structure than
the regular great thing so well I hope
this give you some sort of idea and
flavor of the topics we're going to talk
about in this course we'll start working
from the next lecture in more details on
on ideas of power law networks we'll
talk more about the clustering we'll
talk about more of the ways networks are
structured how they grow and change was
times it was time but for right now
here's a few references that's reading
to get started there are several reviews
well short reviews popular reviews on
articles that will help you to get
started on this topic and this is
several historical papers the paper by
Stanley Stanley Milgram original paper
and then the paper with scheme with Jim
Travers and under a couple newer papers
on the scale of the web well this is it
for today and please if you you know you
remember we started with discussion on
linear algebra and wrap properties and
graph analysis and if you're not very
comfortable with those please spend some
time and refresh those ideas well that's
it for today