Tóm tắt nội dung tài liệu:

aph theory
A necessary course in social network analysis is graph theory. As social
networks can be represented as graphs, understanding fundamental concepts in
graph theories is essential. In this section we will give some concepts that are
often used when analyzing networks. More details can be found at [29].
The degree of a node is defined as the number of ties incident upon that node.
In directed graph, each node has both indegree and outdegree. The indegree is the
number of ties pointing to the node, whereas the outdegree is the number of ties
pointing out from that nodes.
A path is an alternating sequence of nodes and ties, beginning at a node and
ending at a node, and which does not visit any node more than once.
A walk is like a path except that there is no restriction on the number of times
a point can be visited. A path is a kind of walk.
A cycle is just like a path except that it starts and ends at the same point.
The length of a path or walk (or cycle) is defined as the number of ties in it.
A path between two nodes with the shortest length is called a shortest path
(also a geodesic) between the two nodes. It is not always unique (that is, there
may be several paths between the same two points that are equally short). The
graph-theoretic distance between two nodes is defined as the length of the shortest
path between them.
A graph is connected if there exists a path (of any length) from every node to
every other node. The longest possible path between any two nodes in a
connected graph is n-1, where n is the number of nodes in the graph.
~ 13 ~
A node is reachable from another node if there exists a path of any length
from one to the other.
A connected component is a maximal sub-graph in which all nodes are
reachable from every other. Maximal means that it is the largest possible sub-
graph: you could not find another node anywhere in the graph such that it could
be added to the sub-graph and all the nodes in the sub-graph would still be
connected.
For directed graphs, there are strong components and weak components. A
strong component is a maximal sub-graph in which there is a path from every
node to every node following all the arcs in the direction they are pointing. A
weak component is a maximal sub-graph which would be connected if we
ignored the direction of the arcs.
A cutpoint is a vertex whose removal from the graph increases the number of
components. That is, it makes some points unreachable from some others. It
disconnects the graph.
A cutset is a collection of points whose removal increases the number of
components in a graph. A minimum weight cutset consists of the smallest set of
points that must be removed to disconnect a graph. The number of points in a
minimum weight cutset is called the point connectivity of a graph. If a graph has a
cutpoint, the connectivity of the graph is 1. The minimum number of points
separating two nonadjacent points s and t is also the maximum number of point-
disjoint paths between s and t.
A bridge is an edge whose removal from a graph increases the number of
components (disconnects the graph). An edge cutset is a collection of edges whose
removal disconnects a graph. A local bridge of degree k is an edge whose
removal causes the distance between the endpoints of the edge to be at least k.
~ 14 ~
The edge-connectivity of a graph is the minimum number of lines whose removal
would disconnect the graph. The minimum number of edges separating two
nonadjacent points s and t is also the maximum number of edge-disjoint paths
between s and t.
5. Social network’s characteristics
In the late of 1950s, two mathematicians Erdös and Rényi created a great
important theory in graph by modeling many real world networks by a special
type of graph – random graph. To create a random graph with n nodes and m
ties, they put n nodes next to each other, take pair of node at random and tie
them together, the process continues until the graph has m ties. Erdös and Rényi
realize that “when m is small, the graph is likely to be fragmented into many
small clusters” (components), “as m increases the components grow”. For m >
n/2, all nodes are connected to each other [31].
Beside regular and random graph, the two extreme types of graph, network
analysts also study some other types of networks, two most important of them
are small world and scale free networks.
5.1. Small world networks
The experiments conducted by Stanley Milgram and his colleagues for social
networks of people in the United States raising the concept of “small world”. The
phrase captures the initial surprise between two strangers (“What a small
world”) when they realize that they are indirectly connected to one another
through mutual friends. People in Kansas and Nebraska were asked to direct
letters to strangers in Boston by forwarding them to friends who thought might
know the strangers in Boston. And half of the letters were successfully delivered
through no more than five intermediaries. Another experiments show that there
might be “six degrees of separation” between any two individuals in the world.
~ 15 ~
The research was groundbreaking in that it showed that human society is a small
world network characterized by shorter than expected path lengths [16].
In small world network, most nodes can be reached from every other by a
small number of hops or steps.
Figure 6: six degrees of separation
Source:
~ 16 ~
Figure 7: Real world example of small world networks.
(a) science coauthor network, (b) connected pages on a part of the internet, (c)
biochemical pathway network, and (d) New York state electric power grid.
Figure 7 (a), (b), (c) are from
www.nd.edu/~networks/publications.html#talks0001 by Barabasi, Oltvai, Jeong
et al. Figure 6 (d) is from
~ 17 ~
5.2. Scale free networks
Many real world networks are scale free, which means the network will not
change its properties no matter how many nodes it has. The degree distribution
of scale free networks follows the Yule-Simon distribution – a power law
relationship defined by P(k) ~ k-α, where P(k) denotes the probability that a node
in the network connects with k other nodes, the coefficient α may very
approximately from 2 to 3 for most cases, but some times it can takes a value
between 1 and 2 [36].
Scale free networks have some highly connected hubs and the rest of nodes
are of low degree. The hubs are thought to serve some specific purposes in their
networks, although this depends greatly on the domain. The structure of this
kind of network allows the ability of fault tolerant. Because the random
occurrence of failures and the number of small degree nodes are enormous, the
likelihood that a hub would be affected is negligible. Even if such even occurs,
the networks will not lose its connectedness, because of the remaining hubs. This
property make scale free network highly stable and robust [36].
6. Social network analysis – SNA
SNA [15] deals with mapping and measuring the nodes and relations
between the nodes in a social network. As stated previously, the nodes might be
people, organizations, etc, and relations might be friendship, kinship, or water
flow.
Social network analysis has become a key technique in modern sociology,
anthropology, geography, social psychology, sociolinguistics, information
science, communication studies, organizational studies, economics, and biology
as well. For over a century, people have used social network metaphor to model
complex sets of relationships between actors of social systems at all scale.
~ 18 ~
Analysts reason from whole to part, from structure to relation to individual, from
behavior to attitude [33].
So why do we have to study social networks and what we can learn about
their structure? The reason is that the structure of a network affects its
functionalities. For example, the topology of social networks affects the way
diseases spread through a population. Consider a city water distribution
network, delivering water to households via pipes and junctions. Accidental or
malicious instructions can cause contaminants to spread over the network. Jure
Leskovec and colleagues at Carnegie Melon University has proposed an
algorithm to select a few locations to càisensors in order to detect these
contaminants as soon as possible so that it minimizes the population consuming
contaminants [18]. The topology of power grid affects the stability and robustness
of its power transmission; the power failure in Cleveland, Ohio on August 14,
2003 is an example. When occurred, the shutting down of nuclear power plants in
New York State a...

Yêu cầu Download

Tài liệu, ebook tham khảo khác

Ranking in social network – Social rank - pdf 16

Tóm tắt nội dung tài liệu:

Tài liệu, ebook tham khảo khác

Học thêm