Introduction to Introduction to NetworksNetworks
Basic Measures of Networks
Centrality Analysis in Networks
Modeling of Network Formation
Primitives of Social Networks
Networks and Their RepresentationsNetworks and Their Representations
A network/graph: G = (V, E), where V: vertices/nodes, E: edges/links
E: a subset of V × V, n = |V| (order of G), m = |E| (size of G).
Multi-edge: if more than one edge between the same pair of vertices
loop: if an edge connects vertex to itself (., (v i, vi))
Simple network: if a network has neither self-edges nor multi-edges
Adjacency matrix:
Aij = 1 if there is an edge between vertices i and j; 0 otherwise
Directed graph (digraph): if each edge has a direction (tail head) →
Aij = 1 if there is an edge from j to i; 0 otherwise
Weighted graph: If a weight wij (usually a real number) is associated
with each edge vij
Basic Basic NetworkNetwork Structures and Properties Structures and Properties
Subgraph: A subset of the nodes and edges in a graph/network
Given a subset of vertices V’ V, the induced subgraph G’ = (V’, E’)
consists exactly of all the edges present in G between vertices in V’
Clique(complete graph): Every node is connected to every other
Singleton vs. dyad (two nodes and their relationship) vs. triad:
B
C
D
E
F
A
Ego-centric network: A network pull out by
selecting a node and all of its connections
The 1-degree egocentric network of A
The -degree egocentric network of A
The 2-degree egocentric network of A
Vertex Degree for Undirected & Directed NetworksVertex Degree for Undirected & Directed Networks
Let a network G = (V, E)
Undirected Network
Degree (or degree centrality) of a vertex: d(vi)
# of edges connected to it, ., d(A) = 4, d(H) = 2
Directed network
In-degree of a vertex din(vi):
# of edges pointing to vi
., din(A) = 3, din(B) = 2
Out-degree of a vertex dout(vi):
# of edges from vi
., dout(A) = 1, dout(B) = 2
Degree Distribution and PathDegree Distribution and Path
Degree sequence of a graph: The list of degrees of the nodes sorted in
non-increasing order
., in graph G1, degree sequence: (4, 3, 2, 2, 1)
Degree frequency distribution of a graph: Let Nk denote the # of
vertices with degree k
(N0, N1, …, Nt), t is max degree for a node in G
., in graph G1, degree freq. distrib.: (0, 1, 2, 1, 1)
Degree distribution of a graph:
Probability mass function f for random variable X
(f(0), f(1), …, f(t), where f(k) = P(X = k) = Nk/n
., in graph G1, degree distrib.: (0, , , , )
Walk in a graph G between nodes X and Y: ordered sequence of vertices,
starting at X and ending at Y, . there is an edge between every pair of
consecutive vertices
Hops: the length of the walk
Path: a walk with distinct vertices
Distance: the length of the shortest path
Graph G1
Radius and Diameter of a NetworkRadius and Diameter of a Network
Eccentricity: The eccentricity of a node vi is the maximum distance
from vi to any other nodes in the graph
e(vi) = maxj {d(vi, vj)}
., e(A) = 1, e(F) = e(B) = e(D) = e(H) = 2
Radius of a connected graph G: the min eccentricity of any node in G
r(G) = mini {e(vi)} = mini {maxj {d(vi, vj)}}
., r(G1) = 1
Diameter of a connected graph G: the max eccentricity of any node in
G
d(G) = maxi {e(vi)} = maxi, j {d(vi, vj)}
., d(G1) = 2
Diameter is sensitive to outliers. Effective diameter: min # of hops for
which a large fraction, typically 90%, of all connected pairs of nodes
can reach each other.
Graph G1
PathsPaths
Geodesic path: shortest path
Geodesic paths are not necessarily unique: It is quite possible to
have more than one path of equal length between a given pair of
vertices
Diameter of a graph: the length of the longest geodesic path
between any pair of vertices in the network for which a path
actually exists
Eulerian path: a path that traverses each edge in a network exactly once
The Königsberg bridge problem
Hamilton path: a path that visits each vertex in a network exactly once
Other PathsOther Paths
Components in Directed & Undirected NetworkComponents in Directed & Undirected Network
The graph contains 2 weakly connected
and 5 strongly connected components
Weakly connected graph: there is a node in the
graph such that this node can be reached but this
node cannot reach any other nodes except for itself
Out-component of a node n: the subgraph including
any nodes that can be reached by n
In-component of n: the subgraph including any
nodes that can reach n
Independent Paths, Connectivity, and Cut SetsIndependent Paths, Connectivity, and Cut Sets
Two path connecting a pair of vertices (A, B) are edge-independent if they
share no edges
Two path are vertex-independent if they share no vertices other than the
starting and ending vertices
A vertex cut set is a set of vertices whose removal will disconnected a
specified pair of vertices
An edge cut set is a set of edges whose removal will disconnected a
specified pair of vertices
A minimum cut set: the smallest cut set that will disconnect a specified pair
of vertices
Menger’s theorem => maxflow/min-cut theorem: For a pair of vertices,
size of min-cut set = vertex connectivity = maximum flow
This works also for weighted networks
multiple size-2 edge/vertex cut
set
Clustering CoefficientClustering Coefficient
The clustering coefficient of a node vi is a measure of the density of
edges in the neighborhood of vi
Let Gi = (Vi, Ei) be the subgraph induced by the neighbors of vertex vi,
|Vi| = ni (# of neighbors of vi), and |Ei| = mi (# of edges among the
neighbors of vi)
Clustering coefficient of vi for undirected network is
For directed network,
Clustering coefficient of a graph G: Averaging the local clustering
coefficient of all the vertices (Watts & Strogatz):
Co-citation and Bibliographic CouplingCo-citation and Bibliographic Coupling
Co-citation of vertices i and j: # of vertices having
outgoing edges pointing to both i and j
Co-citation of i and j:
Co-citation matrix: It is a symmetric matrix
Diagonal matrix (Cii): total # papers citing i
Bibliographic coupling of vertices i and j: # of other
vertices to which both point
Bibliographic coupling of i and j:
Co-citation matrix:
Diagonal matrix (Bii): total # papers cited by i
Vertices i and j are
co-cited by 3 papers
Vertices i and j cite
3 same papers
Cocitation & Bibliographic Coupling: ComparisonCocitation & Bibliographic Coupling: Comparison
Two measures are affected by the number of incoming and
outgoing edges that vertices have
For strong co-citation: must have a lot of incoming edges
Must be well-cited (influential) papers, surveys, or books
Takes time to accumulate citations
Strong bib-coupling if two papers have similar citations
A more uniform indicator of similarity between papers
Can be computed as soon as a paper is published
Not change over time
Recent analysis algorithms
HITS explores both co-citation and bibliographic coupling
Bipartite NetworksBipartite Networks
Bipartite Network: 1. two kinds of vertices 2.
edges linking only vertices of unlike types
Incidence matrix:
Bij = 1 if vertex j links to group i
0 otherwise
One can create a one-mode project from the
two-mode partite form (but with info loss)
Introduction to Introduction to NetworksNetworks
Basic Measures of Networks
Centrality Analysis in Networks
Modeling of Network Formation
Primitives of Social Networks
Centrality: Basic Measure in a NetworkCentrality: Basic Measure in a Network
Centrality: How “central” a node is in the network
Degree centrality: degree of a node (the higher degree, more
important the node)
Eccentricity centrality: the less eccentric, the more central
c(vi) = 1/e(vi)
Central node: e(vi) = r(G) (if it equals the radius of G)
Periphery node: e(vi) = d(G) (if it equals the diameter of G)
Often used in facility location, ., emergency center
Closeness centrality: the average of the shortest path length
from the node to every other node in the network, indicating
how close a node is to all other nodes in the network
c(vi) = 1/∑j d(vi, vj)
median node vm if vm has the smallest total distance ∑j d(vm, vj)
Facility location, ., shopping center, minimize total distance
Centrality Measures (II)Centrality Measures (II)
Betweenness centrality for a node v: # of shortest paths
from all vertices to all others that pass through v
ηjk: # of shortest paths between vertices vj and vk
ηjk(vi): # of such paths that contain vi
Betweenness centrality of a vertex vi:
Indicating a central “monitoring role played by vi for
various pairs of nodes
Eigenvector centrality: Measure the influence of a node in
a network, ., connections to high-scoring nodes
contribute more to the score of the node in question than
equal connections to low-scoring nodes
Centrality Measures on the Web (I): Centrality Measures on the Web (I):
Eigenvector CentralityEigenvector Centrality
Web: a directed graph, PageRank and HITS are typical
algorithms
Eigenvector centrality, or prestige, importance, or rank of a
node v
The more nodes point to v, the higher v’s prestige
The more prestige of a node pointing to v, the higher v’s
prestige
Let p(u) be prestige score for node u. Then
Written in vector form:
At k-th iteration, we have
Vetor pk converges to the dominant eigenvector of AT with
increasing k
Centrality Measures on the Web (II): Centrality Measures on the Web (II):
PageRankPageRank
Random surfing assumption: A web surfer randomly chooses one of the
outgoing links from the current page or with some very small probability
randomly jumps to any other page in the web graph
Pagerank of a page v : the probability of a random web surfer landing at v
Normalized prestige:
The prob. of visiting a page pointed by v is 1/dout(v), dout is outdegree of v
Compute updated pagerank vector for v,
where N(u, v) is the normalized adjacency matrix of the graph, and
N(u, v) = 1/dout(u) if (u, v) in E or 0 .
Random Jumps: a small prob. jumping to any other node (viewing web as a
fully connected graph, ., adjacency matrix Ar = 1nXn)
Pagerank score computation:
PageRank: Capturing Page PopularityPageRank: Capturing Page Popularity (Brin & Page’98)(Brin & Page’98)
Intuitions
Links are like citations in literature
A page that is cited often can be expected to be more useful in
general
PageRank is essentially “citation counting”, but improves over simple
counting
Consider “indirect citations” (being cited by a highly cited paper
counts a lot…)
Smoothing of citations (every page is assumed to have a non-zero
citation count)
PageRank can also be interpreted as a random surfing model (thus
capturing popularity)
At any page,
With prob. , randomly jumping to a page
With prob. (1 – ), randomly picking a link to follow
Centrality Measures on the Web (III): Centrality Measures on the Web (III):
HITS (HITS (Computing Computing Hub & Authority ScoresHub & Authority Scores))
For a specific query, a page of high Pagerank score may not be that relevant
HITS (Hyperlink Induced Topic Search) computes two values for a page
Authority score: analogous to pagerank/prestige scores
Hub score: based on how many “good” pages it points to
How is HITS query-based?
first uses standard search engines to retrieve the set of relevant pages
then expands the set to include any page that point to or is pointed to by)
some pages in the set
Any pages originating from the same host are eliminated
HITS is only applied on this expanded query-specific graph G
Computation:
In matrix computation (essentially two eigenvector computation):
HITS: Capturing Authorities & Hubs HITS: Capturing Authorities & Hubs (Kleinberg’98)(Kleinberg’98)
Intuitions of HITS (Hyperlink Induced Topic Search)
Pages that are widely cited are good authorities
Pages that cite many other pages are good hubs
The key idea of HITS
Good authorities are cited by good hubs
Good hubs point to good authorities
Iterative reinforcement …
AAT is the co-citation matrix and ATA is the bibliographic
coupling matrix. Authority centrality is eigenvector
centrality for the co-citation network
Metrics (Measures) in Social Network Analysis (I)Metrics (Measures) in Social Network Analysis (I)
Betweenness: The extent to which a node lies between other nodes in
the network. This measure takes into account the connectivity of the
node's neighbors, giving a higher value for nodes which bridge clusters.
The measure reflects the number of people who a person is connecting
indirectly through their direct links
Bridge: An edge is a bridge if deleting it would cause its endpoints to
lie in different components of a graph.
Centrality: This measure gives a rough indication of the social power of
a node based on how well they "connect" the network. "Betweenness",
"Closeness", and "Degree" are all measures of centrality.
Centralization: The difference between the number of links for each
node divided by maximum possible sum of differences. A centralized
network will have many of its links dispersed around one or a few nodes,
while a decentralized network is one in which there is little variation
between the number of links each node possesses.
Metrics (Measures) in Social Network Analysis (II)Metrics (Measures) in Social Network Analysis (II)
Closeness: The degree an individual is near all other individuals in a
network (directly or indirectly). It reflects the ability to access
information through the "grapevine" of network members. Thus,
closeness is the inverse of the sum of the shortest distances
between each individual and every other person in the network
Clustering coefficient: A measure of the likelihood that two
associates of a node are associates themselves. A higher clustering
coefficient indicates a greater 'cliquishness'.
Cohesion: The degree to which actors are connected directly to
each other by cohesive bonds. Groups are identified as ‘cliques’ if
every individual is directly tied to every other individual, ‘social
circles’ if there is less stringency of direct contact, which is
imprecise, or as structurally cohesive blocks if precision is wanted.
Degree (or geodesic distance): The count of the number of ties to
other actors in the network.
Metrics (Measures) in Social Network Analysis (III)Metrics (Measures) in Social Network Analysis (III)
(Individual-level) Density: The degree a respondent's ties know one
another/ proportion of ties among an individual's nominees. Network or
global-level density is the proportion of ties in a network relative to the
total number possible (sparse versus dense networks).
Flow betweenness centrality: The degree that a node contributes to
sum of maximum flow between all pairs of nodes (not that node).
Eigenvector centrality: A measure of the importance of a node in a
network. It assigns relative scores to all nodes in the network based on
the principle that connections to nodes having a high score contribute
more to the score of the node in question.
Local Bridge: An edge is a local bridge if its endpoints share no common
neighbors. Unlike a bridge, a local bridge is contained in a cycle.
Path Length: The distances between pairs of nodes in the network.
Average path-length is the average of these distances between all pairs
of nodes.
Metrics (Measures) in Social Network Analysis (IV)Metrics (Measures) in Social Network Analysis (IV)
Prestige: In a directed graph prestige is the term used to describe a node's
centrality. "Degree Prestige", "Proximity Prestige", and "Status Prestige" are
all measures of Prestige.
Radiality Degree: an individual’s network reaches out into the network and
provides novel information and influence.
Reach: The degree any member of a network can reach other members of the
network.
Structural cohesion: The minimum number of members who, if removed
from a group, would disconnect the group
Structural equivalence: Refers to the extent to which nodes have a common
set of linkages to other nodes in the system. The nodes don’t need to have
any ties to each other to be structurally equivalent.
Structural hole: Static holes that can be strategically filled by connecting one
or more links to link together other points. Linked to ideas of social capital: if
you link to two people who are not linked you can control their
communication
Introduction to Introduction to NetworksNetworks
Basic Measures of Networks
Centrality Analysis in Networks
Modeling of Network Formation
Primitives of Social Networks
Why Network Modeling?Why Network Modeling?
Many real-world networks exhibit certain common
characteristics, even though they come from very different
domains, ., communication, social, and biological networks
A typical network has the following common properties:A typical network has the following common properties:
Few connected components:
often only 1 or a small number, independent of network size
Small diameter:
often a constant independent of network size (like 6)
growing only logarithmically with network size or even shrink?
typically exclude infinite distances
A high degree of clustering:
considerably more so than for a random network
A heavy-tailed degree distribution:
a small but reliable number of high-degree vertices
often of power law form
Common Properties of Real NetworksCommon Properties of Real Networks
Real network: large, sparse (# of edges |E| = O(n), n: # of nodes)
Small-world property: Avg. path length µL scales logarithmically
with n (# of nodes in the graph):
Ultra-small-world property:
Scale-free property (power law distribution): most nodes have
very small degree, but a few hub nodes have high degrees
The probability that a node has degree k:
log-log plot shows a straight line:
Clustering effect: Two nodes are more likely to be connected if
they share a common neighbor
Clustering effect: a high clustering coefficient for graph G
C(k): avg clustering coefficient for nodes with degree k
Power law relationship between C(k) and k:
Probabilistic Models of NetworksProbabilistic Models of Networks
All of the network generation models we will study are
probabilistic or statistical in nature
They can generate networks of any size
They often have various parameters that can be set:
size of network generated
average degree of a vertex
fraction of long-distance connections
The models generate a distribution over networks
Statements are always statistical in nature:
with high probability, diameter is small
on average, degree distribution has heavy tail
Thus, we’re going to need some basic statistics and
probability theory
Power Law (or Pareto) DistributionsPower Law (or Pareto) Distributions
Pareto distribution (heavy-tailed, or power
law):
Pareto(x|k,m) = k mk x–(k+1) I(x ≥ m)
x must be greater than some constant m
but not too much greater
Distributions: mode = m
mean = km/(k-1) if k > 1
Variance = m2k/((k-1)2(k-2)) if k > 2
For variables assuming integer values > 0, probability of value x ~ 1/xα
This is why it is called power law distribution, also referred to as scale-
free
If we plot the distribution on a log-log scale, it forms a straight line
Typically 0 < α < 2; smaller α gives heavier tail
Why long tails or heavy tails? For binomial, normal, and Poisson
distributions, the tail probabilities approach 0 exponentially fast
What kind of phenomena does this distribution model?
Word frequency vs their rank (the, of, …); wealth distribution; …
Distinguishing Distributions in DataDistinguishing Distributions in Data
All these distributions are idealized models
In practice, we do not see distributions, but data
Typical procedure to distinguish between Poisson, power law, …
might restrict our attention to a range of values of interest
accumulate counts of observed data into equal-sized bins
look at counts on a log-log plot
Power law:
log(P(X = x)) = log(1/xα) = – α log(x)
linear, slope –α
Normal:
log(P(X = x)) = log(α exp(–x2/b)) = log(α) – x2/b
non-linear, concave near mean
Poisson:
log(P(X = x)) = log(exp(–l) lx/x!)
also non-linear
Zipf’s LawZipf’s Law
Pareto distribution vs. Zipf’s Law
Pareto distributions are continuous probability distributions
Zipf's law: a discrete counterpart of the Pareto distribution
Zipf's law:
Given some corpus of natural language utterances, the frequency of
any word is inversely proportional to its rank in the frequency table
Thus the most frequent word will occur approximately twice as
often as the second most frequent word, which occurs twice as
often as the fourth most frequent word, etc.
General theme:
rank events by their frequency of occurrence
resulting distribution often is a power law!
Other examples:
North America city sizes
personal income
file sizes
genus sizes (number of species)
Linear scales on both axes Logarithmic scales on both
axes
The same data plotted on linear and logarithmic
scales. Both plots show a Zipf distribution with 300
data points
Zipf DistributionZipf Distribution
Some Models of Network GenerationSome Models of Network Generation
Erdös-Rényi Random graph model:
Gives few components and small diameter
does not give high clustering and heavy-tailed degree distributions
is the mathematically most well-studied and understood model
Watts-Strogatz small world graph model:
gives few components, small diameter and high clustering
does not give heavy-tailed degree distributions
Barabási-Albert Scale-free model:
gives few components, small diameter and heavy-tailed distribution
does not give high clustering
Hierarchical network:
few components, small diameter, high clustering, heavy-tailed
Affiliation network:
models group-actor formation
Erdös-Rényi (ER) Random Graph ModelErdös-Rényi (ER) Random Graph Model
A random graph is obtained by starting with a set of N vertices and
adding edges between them at random
Different random graph models produce different probability
distributions on graphs
Most commonly studied is the Erdős–Rényi model, denoted G(N, p), in
which every possible edge occurs independently with probability p
Random graphs were first defined by Paul Erdős and Alfréd Rényi in
their 1959 paper "On Random Graphs”
The usual regime of interest is when p ~ 1/N, N is large
., p = 1/2N, p = 1/N, p = 2/N, p = 10/N, p = log(N)/N, etc.
in expectation, each vertex will have a “small” number of neighbors
will then examine what happens when N --> infinity
can thus study properties of large networks with bounded degree
Sharply concentrated; not heavy-tailed
The Watts and Strogatz ModelThe Watts and Strogatz Model
Proposed by Duncan J. Watts and Steven Strogatz in their joint 1998
Nature paper
A random graph generation model that produces graphs with small-
world properties, including short average path lengths and high
clustering
The model also became known as the (Watts) beta model after Watts
used β to formulate it in his popular science book Six Degrees
The ER graphs fail to explain two important properties observed in real-
world networks:
By assuming a constant and independent probability of two nodes
being connected, they do not account for local clustering, ., having
a low clustering coefficient
Do not account for the formation of hubs. Formally, the degree
distribution of ER graphs converges to a Poisson distribution, rather
than a power law observed in most real-world, scale-free networks
Barabási–AlbertBarabási–Albert Scale-Free Model Scale-Free Model
Major limitation of the Watts-Strogatz model
It produces graphs that are homogeneous in degree
Real networks are often inhomogeneous in degree, having
hubs and a scale-free degree distribution (scale-free networks)
Scale-free networks are better described by the preferential
attachment family of models, ., the Barabási–Albert (BA)
model
Edges from the new vertex are more likely to link to nodes
with higher degrees
The rich-get-richer approach
This leads to the proposal of a new model: scale-free network, a
network whose degree distribution follows a power law, at least
asymptotically
What Does that Mean?What Does that Mean?
Poisson distribution
Exponential
Network
Power-law distribution
Scale-free
Network
Scale-Free Networks: Major IdeasScale-Free Networks: Major Ideas
The number of nodes (N) is not fixed
Networks continuously expand by additional new nodes
WWW: addition of new nodes
Citation: publication of new papers
The attachment is not uniform
A node is linked with higher probability to a node that
already has a large number of links
WWW: new documents link to well known sites (CNN,
Yahoo, Google)
Citation: Well cited papers are more likely to be cited
again
Generation of Scale-Free NetworkGeneration of Scale-Free Network
Start with (say) two vertices connected by an edge
For i = 3 to N:
for each 1 <= j < i, d(j) = degree of vertex j so far
let Z = ∑ d(j) (sum of all degrees so far)
add new vertex i with k edges back to {1, …, i – 1}:
i is connected back to j with probability d(j)/Z
Vertices j with high degree are likely to get more links! —“Rich get richer”
Natural model for many processes:
hyperlinks on the web
new business and social contacts
transportation networks
Generates a power law distribution of degrees
exponent depends on value of k
Preferential attachment explains
heavy-tailed degree distributions
small diameter (~log(N), via “hubs”)
Will not generate high clustering coefficient
no bias towards local connectivity, but towards hubs
03/01/15
Robustness of Robustness of
Random vs. Scale-Free NetworksRandom vs. Scale-Free Networks
The accidental failure
of a number of nodes
in a random network
can fracture the
system into non-
communicating
islands.
Scale-free networks
are more robust in the
face of such failures
Scale-free networks
are highly vulnerable
to a coordinated
attack against their
hubs
Case1: Internet BackboneCase1: Internet Backbone
(Faloutsos, Faloutsos and Faloutsos, 1999)
Nodes: computers,
routers Links: physical
lines
03/01/15
45
Internet-MapInternet-Map
Introduction to Introduction to NetworksNetworks
Basic Measures of Networks
Centrality Analysis in Networks
Modeling of Network Formation
Primitives of Social Networks
Social NetworksSocial Networks
Social network: A social structure made of nodes
(individuals or organizations) that are related to each other
by various interdependencies like friendship, kinship, like, ...
Graphical representation
Nodes = members
Edges = relationships
Examples of typical social networks on the Web
Social bookmarking ()
Friendship networks (Facebook, Myspace, LinkedIn)
Blogosphere
Media Sharing (Flickr, Youtube)
Folksonomies
Communication NetworksCommunication Networks
The Earth is developing an electronic nervous
system, a network with diverse nodes and links are
-computers
-routers
-satellites
-phone lines
-TV cables
-EM waves
Communication
networks: Many
non-identical
components with
diverse
connections
between them
““Natural” Networks and UniversalityNatural” Networks and Universality
Consider many kinds of networks:
social, technological, business, economic, content,…
These networks tend to share certain informal properties:
large scale; continual growth
distributed, organic growth: vertices “decide” who to link to
interaction restricted to links
mixture of local and long-distance connections
abstract notions of distance: geographical, content, social,
…
Social network theory and link analysis
Do natural networks share more quantitative universals?
What would these “universals” be?
How can we make them precise and measure them?
How can we explain their universality?
Ref: Introduction to NetworksRef: Introduction to Networks
S. Brin and L. Page, The anatomy of a large scale hypertextual Web search
engine. WWW7.
S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, . Kumar, P. Raghavan, S.
Rajagopalan, and A. Tomkins, Mining the link structure of the World Wide
Web. IEEE Computer’99
D. Cai, X. He, J. Wen, and W. Ma, Block-level Link Analysis. SIGIR'2004.
P. Domingos, Mining Social Networks for Viral Marketing. IEEE Intelligent
Systems, 20(1), 80-82, 2005.
D. Easley and J. Kleinberg, Networks, Crowds, and Markets: Reasoning About
a Highly Connected World, Cambridge Univ. Press, 2010.
L. Getoor: Lecture notes from Lise Getoor’s website:
D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the Spread of Influence
through a Social Network. KDD’03.
J. M. Kleinberg, Authoritative Sources in a Hyperlinked Environment, J. ACM,
1999
D. Liben-Nowell and J. Kleinberg. The Link Prediction Problem for Social
Networks. CIKM’03
M. Newman, Networks: An Introduction, Oxford Univ. Press, 2010.
Introduction to Networks
Networks and Their Representations
Basic Network Structures and Properties
Vertex Degree for Undirected & Directed Networks
Degree Distribution and Path
Radius and Diameter of a Network
Paths
Other Paths
Components in Directed & Undirected Network
Slide 10
Independent Paths, Connectivity, and Cut Sets
Clustering Coefficient
Co-citation and Bibliographic Coupling
Cocitation & Bibliographic Coupling: Comparison
Bipartite Networks
Slide 16
Centrality: Basic Measure in a Network
Centrality Measures (II)
Centrality Measures on the Web (I): Eigenvector Centrality
Centrality Measures on the Web (II): PageRank
PageRank: Capturing Page Popularity (Brin & Page’98)
Centrality Measures on the Web (III): HITS (Computing Hub & Authority Scores)
HITS: Capturing Authorities & Hubs (Kleinberg’98)
Metrics (Measures) in Social Network Analysis (I)
Metrics (Measures) in Social Network Analysis (II)
Metrics (Measures) in Social Network Analysis (III)
Metrics (Measures) in Social Network Analysis (IV)
Slide 28
Why Network Modeling?
Common Properties of Real Networks
Probabilistic Models of Networks
Power Law (or Pareto) Distributions
Distinguishing Distributions in Data
Zipf’s Law
Zipf Distribution
Some Models of Network Generation
Erdös-Rényi (ER) Random Graph Model
The Watts and Strogatz Model
Barabási–Albert Scale-Free Model
Slide 40
Scale-Free Networks: Major Ideas
Generation of Scale-Free Network
Robustness of Random vs. Scale-Free Networks
Slide 44
Internet-Map
Slide 46
Social Networks
Slide 48
“Natural” Networks and Universality
Ref: Introduction to Networks
