MODELS FOR EVOLUTION AND JOINING OF
SMALL WORLD NETWORKS
By
SURESH BABU THIPIREDDY
Bachelor of Technology in Computer Science
Jawaharlal Nehru Technological University
Hyderabad, Andhra Pradesh, India
2007
Submitted to the Faculty of the
Graduate College of the
Oklahoma State University
in partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
December, 2009
ii
MODELS FOR EVOLUTION AND JOINING OF
SMALL WORLD NETWORKS
Thesis Approved:
Dr. Subhash Kak
Thesis Adviser
Dr. Venkatesh Sarangan
Dr. Michel Toulouse
Dr. A. Gordon Emslie
Dean of the Graduate College
.
iii
ACKNOWLEDGMENTS
I would like to express my deepest gratitude to my graduate advisor Dr. Subhash
Kak for his guidance and help in completing my work. He has been very inspiring and I
am very grateful for his encouragement and support throughout my graduate studies. I
would also like to thank my graduate committee members Dr. Venkatesh Sarangan and
Dr. Michel Toulouse for their support.
I would like to thank Abhishek, Sandeep and Krishna for their support in finishing
my work and I would also like to thank all my friends who have given me moral support
and friendship.
Finally, I am very much grateful to my parents for their affection, support and
encouragement throughout my life.
iv
TABLE OF CONTENTS
Chapter Page
1. INTRODUCTION………………………………………………………………..1
1.1. Overview……………………………………………………………………..1
1.2. Problem description…………………………………………………………..4
1.3. Proposed method.…………………………………………………………….6
1.4. Rest of the document…………………………………………………………7
2. LITERATURE REVIEW………………………………………………………...8
2.1. Random networks…………………………………………………………….8
2.2. Scale-free networks.………………………………………………………….9
2.3. Small world phenomenon………………………………………………….....9
2.4. Existing model for growing a SWN…………………………………………14
3. METHODLOGY...………………………………………………………………21
3.1.Model for joining networks………………………………………………….21
3.2.Model for growing an existing SWN...……………………………………...28
3.3. Other lattice structures………………………………………………………30
4. RESULTS……………………………………………………………………......34
5. CONCLUSION………………………………………………………………….55
BIBLIOGRAPHY……………………………………………………………………….56
v
LIST OF TABLES
Table Page
4.1 Joining of two small world networks with same number of nodes…………......35
4.2 Joining of two small world networks with different number of nodes…….........37
4.3 Joining of two random networks with same number of nodes………………….39
4.4 Joining of two random networks with different number of nodes………………41
4.5 Joining of a SWN and a random network with same number of nodes…………44
4.6 Joining of a SWN and a random network with different number of nodes……..46
vi
LIST OF FIGURES
Figure Page
1.1 A simple social network…………………………………………………………..2
1.2 Watts and Strogatz model…………………………………………………………3
2.1 Ring lattice structure……………………………………………………………..12
2.2 WS-Model with different probabilities…………………………………………..12
2.3 OHO Model……………………………………………………………………...15
2.4 ZRG Model………………………………………………………………………16
2.5 ZRC Model………………………………………………………………………18
2.6 ZZSG Model……………………………………………………………………..19
2.7 SAV Model………………………………………………………………………20
3.1 Adjacency matrix representation of a SWN with 10 nodes……………………...23
3.2 Adjacency matrix representation of a SWN with 20 nodes……………………...24
3.3 Adjacency matrix representation of a SWN with 30 nodes……………………...24
3.4 Joining of two networks…………………………………………………………27
3.5 Growth of an existing SWN……………………………………………………..29
3.6 Square lattice structure…………………………………………………………..30
3.7 Rewired square lattice structure…………………………………………………31
3.8 Hexagonal lattice structures……………………………………………………..32
3.9 Rewired hexagonal lattice structures……………………………………………33
vii
4.1 Probability Vs Clustering coefficient for joint network formed by joining
two SWNs with same number of nodes………………………………………….36
4.2 Probability Vs Average path length for joint network formed by joining
two SWNs with same number of nodes………………………………………….37
4.3 Probability Vs Clustering coefficient for joint network formed by joining
two SWNs with different number of nodes……………………………………...38
4.4 Probability Vs Average path length for joint network formed by joining
two SWNs with different number of nodes……………………………………...38
4.5 Probability Vs Clustering coefficient for joint network formed by joining
two random networks with same number of nodes……………………………...40
4.6 Probability Vs Average path length for joint network formed by joining
two random networks with same number of nodes……………………………...41
4.7 Probability Vs Clustering coefficient for joint network formed by
joining two random networks with different number of nodes…………………..42
4.8 Probability Vs Average path length for joint network formed by
joining two random networks with different number of nodes…………………..43
4.9 Probability Vs Clustering coefficient for joint network formed by
joining a SWN and a random network with same number of nodes………….....45
4.10 Probability Vs Average path length for joint network formed by
joining a SWN and a random network with same number of nodes…………….45
4.11 Probability Vs Clustering coefficient for joint network formed by
joining a SWN and a random network with different number of nodes…………47
viii
4.12 Probability Vs Average path length for joint network formed by
joining a SWN and a random network with same number of nodes…………….47
4.13 Nodes being added Vs Clustering coefficient for a growing SW network……...49
4.14 Nodes being added Vs Average path length for a growing SW network………..50
4.15 Probability Vs Clustering coefficient for a rewired square lattice structure
with 25 nodes and 100 nodes…………………………………………………….51
4.16 Probability Vs Average path length for a rewired square lattice structure
with 25 nodes and 100 nodes……………………………………………………52
4.17 Probability Vs Clustering coefficient for a rewired two layered and three
layered hexagonal lattice structure………………………………………………53
4.18 Probability Vs Average path length for a rewired two layered and three
layered hexagonal lattice structure………………………………………………54
1
CHAPTER 1
INTRODUCTION
1.1 OVERVIEW OF SOCIAL NETWROKS
Complex networks serve as model of problems in fields of science ranging from
biology to computer science. Such networks are structures consisting of nodes connected
by edges. Some of the examples include the Internet which is a network of domains, the
World Wide Web which is a network of websites, the brain which is a network of
neurons, and an organization which is a network of people.
A social network is a social structure represented by a set of nodes which are
connected based on interdependencies such as friendship, business, like or dislike. Such a
network is characterized by properties like clustering coefficient, degree, shortest path
and diameter. A sample social network is shown below.
Figure-1.1 A simple social network (showing nodes connected to each other)
2
Degree of a social network is the number of edges connected to a node.
Local clustering is the extent to which an individual’s friends are each other’s friends.
Diameter of a network is the maximum of the shortest paths between every node in a
network.
The randomness of a complex structure is an important area of research as it
affects the properties of a network. For many years there was an assumption that
networks can be represented as regular graphs [16]. But in the late 1950s, Erdos and
Renyi (ER), made an important contribution to classical mathematical graph theory [17].
They described a network with complex topology by a random graph, and laid foundation
for random network theory. Although most real world networks are neither completely
regular nor completely random, the ER model proposed by Erdos and Renyi was a
sensible one and it dominated research in several application areas for about half a
century [16].
In the past few years, a large collection of data on various real world networks has
been stored in huge databases because of the computerization of data entry and growth in
computational power. These large databases have helped researchers to analyze the
properties of complex networks. Two significant insights that have emerged from the
study of these databases are the small-world effect and the scale-free feature of most
complex networks [16].
In 1998, in order to describe the transition from a regular lattice to a random
graph, Watts and Strogatz (WS) introduced the concept of small-world network [10],
3
which is characterized by small diameter. It is notable that the small-world phenomenon
is very common. Regular lattices, which are the starting point for the Watts and Strogatz
model, are clustered but do not exhibit the small-world effect i.e., the shortest path
between every pair of nodes is high. Conversely, random graphs show the small-world
effect, but do not show clustering i.e., the probability that the friends of a node are friends
of each other is low. Thus, both the regular lattice model and the ER random model do
not possess the important property of real networks. Most real-world networks are neither
completely regular nor completely random. The reality is that people usually know their
neighbors, but their circle of acquaintances may not be confined to those who live right
next door, as the lattice model would imply [16]. And also networks formed on the
internet are not created at random. So, the study of the small world networks has received
a lot of attention within a short period of time.
A sample small-world network is shown in the figure below:
Figure-1.2 Watts and Strogatz model with probability p=0.32
4
Another significant discovery in the field of complex networks is the observation
that many large-scale complex networks are scale-free and exhibit power law distribution
[3]. It was argued by Barabasi and Albert that many existing models fail to take into
account important properties of most real network. Real world networks are open, i.e., the
numbers of nodes keep growing over a period of time, thereby increasing the size of the
network. Furthermore, uniform probabilities are assumed for both the random graph and
small-world models while creating new edges [16], which is not realistic. Scale free
networks are formed based on two mechanisms: 1) Population growth, in this real
networks grow in time as new members join the network; and 2) Preferential attachment,
in this newly arriving node will tend to connect to already well-connected nodes. A
significant recent discovery is the observation that a number of large-scale complex
networks, including the Internet, WWW, and metabolic networks, are scale-free and their
connectivity distributions have a power-law form.
1.2 PROBLEM DESCRIPTION
Small-world networks describe many real-life networks, such as the World Wide
Web, communication networks, the electric power grid, or social networks that achieve
both a strong local clustering and a small average path length [12]. Small-world networks
are characterized by two main properties. First, is the characteristic path length, L, which
measures the separation between any two nodes in the graph, averaged over all pair of
nodes; it has been found that L grows slowly as the size of the network increases. Second,
is the clustering coefficient, C, which measures the cliquishness of a neighborhood. The
clustering Ci of node i is defined by Ci = qi / [ ki (ki-1)/2] where qi is the total number of
5
links between the ki neighbors of node i and ki (ki-1)/2 is the maximum number of links
that could exist between ki nodes [12].
The small world networks generated by the Watts and Strogatz (WS) model have
been influential in the field of social networks. Since, the transition from a regular lattice
to a small world network shown in WS was the first of its kind; researchers have
modified this model in different ways. In the WS model rewiring was done on a ring
lattice using a probability p. The main drawback of the Watts and Strogatz simulation
was that the number of nodes in the network was fixed. Since real world networks grow
over a period of time, the generation of growth algorithm is an important research topic.
A few researchers have proposed different models to generate a growing network
which exhibit the properties of small world. For example, the OHO model [11] is initially
in the form of a circle consisting of three nodes which are connected to each other. Then,
a new node is randomly placed on the circle and is connected to m geographically closest
neighbors.
Li Yong et al proposed a new algorithm which is known as SAV algorithm [15].
The purpose of this algorithm was to generate a small world network from a ring lattice
structure. This algorithm offered a different method of generating a small world network,
but growth of the network was not considered. The algorithm initially has a fixed number
of nodes in the form of a ring lattice.
The above models either generate a network using a ring lattice or grow a network
with a basic assumption that the network starts with three nodes arranged in the form of a
triangle. Not much research has been done to generate an evolving small world network
in which a small world network is generated initially and then this small world network is
6
grown gradually. It is possible in the real world networks that instead of growing a small
world network node by node, a group of nodes join to form a network and then get
attached to a small world network. The network that is being attached could be of any
kind.
1.3 PROPOSED METHOD
In this study, we investigate different methods to join two existing networks. We
consider different combinations of networks like small world-small world, small world-random
and random-random. These combinations are considered with structural aspects
like connecting to a well established member of a network, active communities in a
network and finding new or old friends in a network.
We also propose a model for growing an existing small world network. Here we
initially generate a small world network and then grow it using a growth model as new
nodes join the network. We also consider communities of nodes in which we establish
connection between the new node and the existing nodes of a network.
Finally, we look at new lattice models different form the ring lattice structure
considered in the Watts and Strogatz small world simulation.
7
1.4 REST OF DOCUMENT:
In chapter 2, we provide brief literature review and work done in this area. Chapter 3
gives a description of the proposed models and chapter 4 presents the results of our
simulations. Chapter 5 presents our conclusions.
8
CHAPTER 2
LITERATURE REVIEW
2.1 RANDOM NETWORKS
Erdos and Renyi introduced random graphs in 1950s [1],[2]. The Erdos-Renyi
random graph consists of n isolated nodes and an edge is constructed between every pair
of nodes with a probability p. A random graph can be represented by G(n,p), where n is
the number of node in the network and p is the probability for an edge to be constructed
between two nodes.
In the Erdos-Renyi graph, the probability that the degree of a node t in a network
is given by the binomial distribution:
P (t) = Ct
n-1pt(1-p)n-1-t
The average degree of a node is expressed as z = (n-1)p. By expressing
probability p in terms of z, after re-writing the above equation, the degree distribution is
expressed as:
P (t) = Ct
n-1(z/n-1)t(1-(z/n-1))n-1-t
The above equation may be approximated to P (t) = (zt/t!) e-z. Thus the degree
distribution for the nodes follows Poisson distribution.
9
2.2 SCALE-FREE NETWORKS
Scale–free networks were introduced by Barabasi and Albert (BA) in 1999 [3],
[4] and the degree distribution of these graphs follows power law distribution. They
proposed a simple mathematical model with two mechanisms: population growth and
preferential attachment. The mechanism of the population growth is that real networks
grow in time as new members join the network and the mechanism of the preferential
attachment is that newly arriving node tends to connect to already well connected nodes
rather than poorly connected nodes. Barabasi and Albert defined the probability p(ki) of
an existing node i with ki links receiving a new link as below:
p(ki) = cki ; where c is normalized constant.
In a BA graph, the probability that the degree of a node d is given by P(d)=c/dα
for some positive constants c and α. Typically, 2 ≤ α ≤ 3. The probability that the new
node is connected to a given existing node i is given by
P(di) = di/ Σj
i-1 dj where dj is the degree at the node j.
2.3 SMALL WORLD PHENOMENON
The small world phenomenon was discussed first in the late 1950s by political
scientist Ithiel de Sola Pool and mathematician Manfred Kochen [5]. Pool and Kochen
formulated many questions that have come to define the field of social networks:
1) How many other people does each individual in a network know? In other
words what is the person’s degree in the network?
10
2) What is the probability that two people chosen at random from the population
will know each other?
3) What is the chance that they have a friend in common?
4) What is the chance that shortest chain between them requires two
intermediates? Or more than two?
Pool and Kochen’s work provided the inspiration for, among other things, the
famous “Small world” experiment conducted in 1960s by Stanley Milgram [8]. The small
world phenomenon, demonstrated experimentally by Stanley Milgram says that most
humans are connected by chains of friendships that have roughly six individuals in them.
This experiment is famously known as “Six degree of separation”.
This experiment was carried out by asking people in American cities like Wichita
and Omaha to send letters to specifically named East-coast individuals who were not
known to the senders. A condition placed on each sender was that he or she could only
mail the letter to someone with whom the sender was on a first-name basis. The same
condition was placed on each recipient of the letter – he or she could only mail the letter
to a friend with whom he or she was on a first name basis and who appeared to be most
likely to route the letter to its final destination. When Milgram examined the mail chains
that were completed successfully in this manner, he discovered that, on the average, each
letter took six steps between the original sender and the target.
Although Milgram’s experiments created a lot of excitement, it is important to
note that only a few chains started in these experiments were completed. Non-completion
of the chains does not mean that the small world phenomenon does not exist. It is easy to
11
understand why most chains would not be completed. Many people receiving a letter
must have ignored them thinking as a chain letters and those who took the chain letters as
serious might still have ignored them as it is too much of a bother to mail the letter again.
In 1998, Duncan Watts and Steven Strogatz published a “Small world” computer
simulation [10], which goes a step further. The simulations do capture the fact that any
two individuals in a network are connected, on the average, by a small chain. However,
in addition to measuring the average length of the shortest chain connecting any pair of
individuals, Watts and Strogatz also measured the local clustering as would be perceived
by any individual locally. By local clustering it means the extent to which an individual’s
friends are each other’s friends.
Structured and random graphs are characterized by two properties: 1) diameter of
the graph; and 2) clustering coefficient of the graph. The diameter of a graph is the
maximum value of the shortest path between any two nodes or is also the often
considered as the average value of the shortest path between every pair of nodes in the
graph. The clustering coefficient of a graph measures the average extent to which the
immediate neighbors of any node are also each other’s immediate neighbors.
Watts and Strogatz carried out their simulations on a ring lattice. The total number
of nodes in a network is assumed to be N and each node has k local contacts. For
example, if the value of k is set as 4, then it implies that each node is connected to only 4
other nodes in the network.
12
The basic ring lattice network with N=20 nodes and k=4 neighbors is shown below
Figure-2.1 Ring lattice structure
A small world network is created by rewiring the basic diagram shown above in which
each node is connected directly to its immediate neighbors and to a few additional
neighbors in its vicinity. The extent of rewiring is controlled by the probability p.
The small-world graph of Watts and Strogatz model with different probabilities are
shown below:
(a) (b)
13
(c) (d)
(e) (f)
Figure-2.2 WS-Model with different probabilities
(In the above figure (Figure-2.2) small world graphs with different probabilities are
shown. For (a) value of p is 0, for (b) p is 0.08, for (c) p is 0.32, for (d) p is 0.5, for (e) p
is 0.75 and for (f) p is 1), where p is the probability.
14
When the value of p is 0, there wouldn’t be any change in the basic ring structure
and as the p value increases the edges are randomly rewired. When the value of p reaches
1 in the simulation, we get a random graph like an Erdos-Renyi graph. When p=1 the
graph obtained will have a smaller diameter and the local clustering of the nodes will be
destroyed. When p=0, the diameter of the graph becomes large which would be directly
proportional to the number of nodes in the graph and the clustering of nodes will also be
large. A network is a small world network if it has a large clustering coefficient and a
small diameter.
2.4 EXISTING MODELS FOR GROWING SMALL WORLD NETWORKS
The small world network constructed by Watts and Strogatz illustrates the small
world properties in a simple way. However, the small world property is considered to be
much more general than the network shown in previous examples. Ozik et al [11]
introduced a simple mechanism (OHO model) for the evolution of the small world
networks. In this model connections are made purely local and the network growth leads
to stretching of old connections and to high clustering.
In OHO model, the formation of links between nodes is formed based on
geographically local processes [11]. That is, when a new node appears, it forms links
only to those pre-existing nodes that are geographically close to it. In spite of the link
formation being exclusively local, long range links will be shown to arise as a result of
network growth. This in addition to the clustering induced by local connections yields the
small world property.
15
Initially, OHO model has m+1 all-to-all connected nodes on the circumference of the
circle. At each subsequent discrete time step network is grown according to the following
prescription: a) new node is placed in a randomly chosen inter node interval along the
circle circumference, where all intervals have the same probability of being chosen; b)
the new node makes m links to its m previously existing nearest neighbors. Nearest here
refers to the distance measured in number of intervals along the circumference of the
circle. These steps are repeated until the network has grown to a desired number of
nodes.
The graphical representation of the above model is shown below:
Figure-2.3 OHO model
16
Most previous models of small-world networks are stochastic. Zhong Zhi Zhang,
Li Li Rong and Chong Hui Guo (ZRG) presented a model that generates a small-world
network in a simple deterministic way [12]. This model is a growing network, whose size
(the number of nodes) increases exponentially with time.
Let network after t step evolution be denoted by N (t). The network is created by
an iterative method. Its construction algorithm is the following: For t = 0, N (0) is a
triangle whose three nodes connect to one another. For t ≥ 1, N (t) is obtained from N (t −
1) by adding for each edge created at step t − 1 a new node and attaching it to both end
nodes of the edge. In the evolution process of the model, for each new node added, two
new edges are created. And for each of the newly-created edges, a node will be created
and connected to both the ends of the edge in the next step.
The diagrammatic representation of the above ZRG model is shown in Figure-2.4.
Figure-2.4 ZRG model
17
Z. Z. Zhang, L. L. Rong and F. Comellas (ZRC) came up with a model [13],
which is a slight variation of the OHO model. It is a minimal extended evolving model
for small-world networks which is controlled by a parameter q.
Here a model for growing network, constructed in an iterative manner, is
described. The network after t time steps is denoted by N (t). The network starts from an
initial state (t = 0) of m + 1 (m even) nodes distributed on a ring, all of which are
connected to one another by m (m + 1)/2 edges. For t = 1, N (t) is obtained from N (t − 1)
as follows: for each inter node interval, along the ring of N (t − 1), with probability q, a
new node is created and connected to its m nearest neighbors (m/2 on either side),
previously existing at step t −1. Distance, in this case, refers to the number of intervals
along the ring.
When q = 1 and m = 2, the network is reduced to the deterministic ZRG model. If
q <1, the network grows randomly. In particular, as q approaches zero (without reaching
this value) the model coincides with the OHO model, where at each time step, only one
interval is chosen. With every interval having the same probability of being selected, then
a node is placed in the chosen inter node interval and linked to its m nearest.
18
The diagrammatic representation of a network generated from the above process with
q=1 and m=2 is as below:
Figure-2.5 ZRC model
A growing model which interpolates between one-dimensional regular lattice and
small-world networks was proposed by Zhong Zhi Zhang, Shuigeng Zhou, Zhen Shen
and Jihong Guanc (ZZSG) [14]. The model undergoes an interesting phase transition
from large to small worlds.
The model is constructed in the following way:
(i) Initial condition: Start from an initial state (t =2) of three nodes distributed on a ring,
all of which form a triangle.
(ii) Growth: At each increment of time, a new node is added, which is placed in a
randomly chosen inter-node interval along the ring. Then perform the following two
operations.
a) Addition of edges: The new node is connected to its two nearest nodes (one on
either side) previously existing. Nearest, in this case, refers to the number of
intervals along the ring.
19
b) Removal of an edge: With probability q, remove the edge linking the two nearest
neighbors of the new node.
(iii) The growing processes are repeated until the network reaches the desired size.
There are two limiting cases of the present model. When q=1, the network is reduced to
the one dimensional ring lattice. For q=0, no edge is deleted, the model coincides with a
special case m=2 of the OHO model for small-world networks.
The diagrammatic representation of above model is as below:
Figure-2.6 ZZSG model
20
Li Yong, Fang Jin-Qing, Liu Qiang, and Liang Yong proposed an algorithm
known as “spread all over vertices”, which is used for generating small world networks
from ring lattices [15]. During the rewiring in the ring lattice network the degree of the
nodes does not change. The SAV algorithm for constructing small-world network is as
below:
Start with a ring of N nodes, each connected to its k nearest neighbors by
undirected edges. For clarity, N = 10 and k = 4 are considered.
At each time step perform one of the following three operations:
• Randomly select a node i. From the nodes connected with the node i, randomly
select a node j and remove the edge connected to the node i.
• From the nodes unconnected with the node i, randomly select a node u and
connect a new edge to the node i.
• From the nodes connected with the node u, randomly select a node v and remove
the edge connected to the node u.
• For the node v connect a new edge to the node j.
The diagrammatic representation of the above model is as shown below:
Figure-2.7 SAV model
21
CHAPTER 3
METHODOLOGY
In this chapter we provide a description of our main work. We will examine a
model for joining two arbitrary networks and study its properties. We also observe the
properties of joint network that is being generated. We then look at a model for growing
an existing small world network and see how the properties of the network vary. Lastly
we study the properties of a networks generated by rewiring square and hexagonal
lattices.
3.1 MODEL FOR JOINING NETWORKS
Some of the structural reasons for joining two social networks are: to connect to
an established node on other network, to join interested groups, to meet new people and
to find old friends. A normal way to achieve the above requirements is to connect the
nodes of one network to the nodes of other network based on uniform probability. Here
we generate the joint network assuming degree, clustering coefficient, average path
length of the nodes in each network are known.
22
Below are the different conditions:
1) In order to connect to an established node, the nodes of one network are
connected to the nodes of other network based on the degree of each node in the
other network (say if degree of a node is greater than the average degree of the
network, deg>average deg).
2) In order to join an interested group with active communication between its
members, the nodes of one network are connected to the nodes of other network
based on the clustering coefficient of each node in the other network (say if the
clustering coefficient of a node is greater than the average clustering coefficient of
the network, cc>average cc).
3) In order to meet new people or to find an old friend, the nodes of one network are
connected to the nodes of other network based on the average path length of each
node in the other network (say if average path length of a node is greater than the
average of average path lengths of a network, apl<average apl).
When two networks are joined based on the above structural aspects, a new network is
evolved. The initial steps for joining two networks are same for all the above described
criteria’s.
1) Consider two networks, say network1, network2. These networks can be a small
world networks or random networks or one each.
2) Let N1 be number of nodes in network1 and N2 be the number of nodes in
network2. Assume that the network1 is represented by an adjacency matrix with
N1 rows and N1 columns and network2 is represented by an adjacency matrix
with N2 rows and N2 columns.
23
3) For each network, find the degree, clustering coefficient and Average path length
at each node. And also the Average of degrees of all nodes, Average of clustering
coefficient of all nodes and Average of average path length.
4) Now, construct a joint network with N nodes, where N= N1+N2. Joint network is
represented by an adjacency matrix with N rows and N columns.
The representation of networks in the form of a matrix is shown below:
A small world network generated from a ring lattice with N1=10 nodes (each node
connected to k=4 neighbors, k/2 on each side) and a rewiring probability 0.55 in the form
of a matrix is as below:
Figure-3.1 Adjacency matrix representation of a SWN with 10 nodes
Another small world network generated from a ring lattice with N2=20 nodes (each node
connected to k=4 neighbors, k/2 on each side) and a rewiring probability 0.55 in the form
of a matrix is as below:
24
Figure-3.2 Adjacency matrix representation of a SWN with 20 nodes
An initial joint network formed by joining the above two networks with N=30 nodes:
Figure-3.3 Adjacency matrix representation of a SWN with 30 nodes
25
Evolution of a joint network in a normal way:
• Consider the initial joint network formed by joining the two networks.
• For each node in network1 based on a probability P, we connect an edge to a node
selected preferentially from the network2. The preference for each node in
netowrk2 is given by the below equation:
Preference[i] = deg[i]/maximum degree in network2
• For each node in network2 based on a probability P, we connect an edge to a node
selected preferentially from the network1. The preference for each node in
network1 is given by the below equation:
Preference[i] = deg[i]/maximum degree in network1
Evolution of the joint network based on structural aspects:
• Consider the initial joint network formed joining the two networks.
• Select one method from the below structural aspects
1) Evolution of joint network based on degree
• Select the nodes from network1 which has a degree > average degree of
the network1 and say these nodes as set1.
• Select the nodes form network2 which has a degree > average degree of
the netowrk2 and say these nodes as set2.
2) Evolution of joint network based on clustering coefficient
• Select the nodes from network1 which has a clustering coefficient >
average clustering coefficient of the network1 and say these nodes as set1.
26
• Select the nodes form network2 which has a clustering coefficient >
average clustering coefficient of the netowrk2 and say these nodes as set2.
3) Evolution of joint network based on average path length
• Select the nodes from network1 which has an average path length <
average of average path length of the network1 and say these nodes as
set1.
• Select the nodes form network2 which has an average path length <
average of average path length of the netowrk2 and say these nodes as
set2.
• For each node in network1 based on a probability P, we connect an edge to a node
selected preferentially from the set2. The preference for each node in set2 is given
by the below equation:
Preference[i] = deg[i]/maximum degree in set2
• For each node in network2 based on a probability P, we connect an edge to a node
selected preferentially from the set1. The preference for each node in set1 is given
by the below equation:
Preference[i] = deg[i]/maximum degree in set1
The probability P for a node k in a network is given by
P (k) = deg[k] /maximum degree in the network
Then, the properties of the network after establishing the connections between the two
networks are observed.
27
A small world network and a random network with 20 nodes each are considered
initially. Then in each network nodes with its degree greater than the average degree of
the network are selected (these nodes are shown red in color). Then for each node in a
network based on a probability an edge is connected to one of the node selected above
preferentially in other network. After going through every node in both the networks, a
joint network is evolved.
Figure-3.4 Joining of two networks
28
3.2 MODEL FOR GROWING AN EXISTING SMALL WORLD NETWORK
Method description:
• Initially consider a small world network, say network1.
• Let N1 be number of nodes in network1. The network1 is represented by an
adjacency matrix with N1 rows and N1 columns.
• Find the degree, clustering coefficient and Average path length at each node. And
also the Average of degrees of all nodes, Average of clustering coefficient of all
nodes and Average of average path length of the network.
• Below are possible conditions to grow a network:
1) Let n be new node, connect the new node preferentially to (Average
degree) number of nodes from the network1.
2) Find the nodes with degree > Average degree of the network. Let n be new
node, connect the new node preferentially to (Average degree) number of
selected nodes.
3) Find the nodes with clustering coefficient > Average clustering coefficient
of the network. Let n be new node, connect the new node preferentially to
(Average degree) number of selected nodes.
4) Find the nodes with average path length > Average of average path
length’s of the network. Let n be new node, connect the new node
preferentially to (Average degree) number of selected nodes.
• After considering one of the above methods, we then establish a link between the
pairs of selected nodes using the linear function probability.
29
Diagrammatic representation of the growth of an existing small world network is shown
in Figure-3.5.
Initially a small world network with N nodes is generated, then the nodes with
clustering coefficient greater than the average clustering coefficient of the network are
selected (shown red in color in the below diagram). When a new node n arrives, it then
connects to the (average degree) nodes selected above. Later an edge is connected
between pairs of selected nodes (yellow line) based on a linear function probability.
Figure-3.5 Growth of an existing SWN
30
3.3 OTHER LATTCIE STRUCTURES
The basic structure of Watts and Strogatz model is a ring lattice structure, which
is then rewired to form a small world network. Here we study the square lattice structure
and as well as hexagonal structure. We find the initial properties of the square lattice and
hexagonal lattice structure and see how these properties vary as we rewire those
structures.
SQUARE LATTICE
We consider a square lattice with N-rows and N-rows, on which we can assume N
square number of nodes. In the initial state nodes on the corners of the square structure
are connected to 2 nearest neighboring nodes, nodes on the first, last row and first, last
column except the nodes on the corner are connected to 3 nearest neighboring nodes and
every other node is connected to 4 nearest neighboring nodes.
A sample square lattice structure with nodes arranged on it is shown below:
Figure-3.6 Square lattice structure
31
We then rewire every edge based on a probability P and see how the properties of the
resulting structure is being affected.
A sample figure showing resulting structure after rewiring the square lattice with a
probability of P = 0.2 is shown in Figure-3.7.
Figure-3.7 Rewired square lattice structure
This resulting figure is more randomized in structure with a reduced average path length
and increased clustering coefficient.
32
HEXAGONAL LATTICE STRUCTURE
Initially, we have only one hexagon, on which we can place six nodes. Then we
expand the hexagons outwards, which looks like a second layer of hexagons and with this
second layer we can accommodate another 18 nodes. In a similar fashion we can have a
third layer of hexagons; with this we can accommodate another 30 nodes.
The structures discussed above are shown below:
Figure-3.8 Hexagonal lattice structures
Having a look at these structures, we can assume that the nodes on the inner most
or central hexagon to be on circle and the nodes on second layer of hexagons to be on
another circle on top of the inner circle and similarly the nodes on the third layer of
hexagons to be on a third circle on top of both circles. Thus the hexagonal structure
resembles the structure with three circles one on top of other with some interconnections
between the circles.
33
We consider the above hexagonal structure and rewire every edge with a probability P.
The resulting structure is more random and the properties of the resulting structure vary a
bit.
Below are the structure formed after rewiring the above two hexagonal structures with a
probability P=0.5.
Figure-3.9 Rewired hexagonal lattcie structures
34
CHAPTER 4
RESULTS
In this chapter we show the results of joining two networks and see the properties of the
joint network. We have run the simulations based on the structural aspects of joining the
networks and different combinations of networks. We also show the results of growing an
existing small world network. Then, we give brief description of the properties of rewired
square and hexagonal lattice structures.
JOINING OF TWO NETWORKS
Two individual networks are joined to form a joint network based on different
structural aspects such as connecting to a person with lots of friends, joining a group
where there is an active interaction between the members of the group and connecting to
an old friend or finding new friend. In order to achieve the above structural requirements
while joining the two networks, we use the average degree, average clustering coefficient
and average path length of the network.
We join different combinations of small world networks and random networks,
like small world-small world, random–random and small world–random. The
characteristics of individual networks and the joint network for different combinations of
the networks are described in the form of tables and graphs. Tables in each section show
35
the properties of the individual networks and joint networks with probability P for three
different structural aspects. In all the tables N1 represents the number of nodes in
network1, N2 represent nodes in network2 and N represents nodes in the joint network.
The properties of each set of nodes are simulated thrice, first based on the average degree
of the networks, second based on the average clustering coefficient of the networks and
third based on the average path length of the networks. The graphs in all the sections
below show how the properties of the joint network vary for different values of
probability.
Joining two small world networks:
The different scenarios that we consider here are: 1) Two small world networks with
equal number of nodes, and 2) Two small world networks with unequal number of nodes.
Table-4.1 shows the properties of the individual small world networks with equal number
of nodes and joint network formed by joining two small world networks with equal
number of nodes.
Small world network1 Small world network2 Joint Network (P)
N1 Avg_cus Avg_apl N2 Avg_cus Avg_apl N Avg_cus Avg_apl
50
0.088 3.13
50
0.185 3.14
100
0.159 3.41
0.152 3.22 0.176 3.17 0.188 3.68
0.090 3.14 0.21 3.30 0.137 3.41
0.157 3.98 0.153 3.92 0.144 3.71
36
100 0.154 3.81 100 0.177 3.90 200 0.112 3.90
0.118 3.85 0.117 3.79 0.088 4.03
200
0.145 4.54
200
0.156 4.53
400
0.110 4.24
0.136 4.51 0.080 4.33 0.102 4.29
0.096 4.48 0.140 4.58 0.102 4.49
Table-4.1: Joining of two small world networks with equal number of nodes
Figure-4.1: Probability Vs Clustering coefficient for joint network formed by joining two
SWNs with equal number of nodes
50-50,
100-100,
200-200
Based on CC Based on APL
37
Figure-4.2: Probability Vs Average path length for joint network formed by joining two
SWNs with equal number of nodes.
Table-4.2 shows the properties of the individual small world networks with
unequal number of nodes and joint network formed by joining two small world networks
with unequal number of nodes.
Small world network1 Small world network2 Joint Network (P)
N1 Avg_cus Avg_apl N2 Avg_cus Avg_apl N Avg_cus Avg_apl
50
0.164 3.23
100
0.170 3.83
150
0.174 3.54
0.151 3.13 0.136 3.82 0.120 3.45
0.163 3.28 0.154 3.80 0.123 3.54
50
0.164 3.25
200
0.116 4.40
250
0.124 3.47
0.088 3.20 0.144 4.50 0.113 3.63
0.243 3.27 0.119 4.46 0.132 3.77
100
0.180 3.89
200
0.09 4.35
300
0.112 3.92
0.132 3.85 0.101 4.40 0.109 4.06
50-50,
100-100,
200-200
Based on degree Based on CC Based on APL
38
0.082 3.65 0.138 4.50 0.137 4.04
Table-4.2: Joining of two small world networks with unequal number of nodes
50-100,
50-200,
100-200
Figure-4.3: Probability Vs Clustering coefficient for joint network formed by joining two
SWNs with unequal number of nodes
50-100,
50-200,
100-200
Figure-4.4: Probability Vs Average path length for joint network formed by joining two
SWNs with unequal number of nodes
Based on degree Based on CC Based on APL
Based on degree Based on CC Based on APL
39
By looking at the properties of the joint network formed by joining two small
world networks with equal numbers of nodes, we can see that the clustering coefficient of
the joint network decreases initially for low probability values and increases as the
probability increases. The average path length of the joint network decreases gradually as
the probability increases. The same results were observed with unequal number of nodes
also. These properties of a joint network formed in both cases are similar to that of the
small world model.
Joining two random networks:
The different scenarios that we consider here are: 1) Two random networks with
equal number of nodes, and 2) Two small random with unequal number of nodes.
Table-4.3 shows the properties of the individual random networks with equal number of
nodes and joint network formed by joining two random networks with equal number of
nodes.
Random network1 Random network2 Joint Network (P)
N1 Avg_cus Avg_apl N2 Avg_cus Avg_apl N Avg_cus Avg_apl
50
0.036 3.20
50
0.076 3.08
100
0.073 3.18
0.053 3.14 0.399 3.10 0.107 3.35
0.076 3.07 0.075 3.08 0.092 3.40
0.020 3.60 0.055 3.63 0.047 3.72
40
100 0.047 3.62 100 0.081 3.70 200 0.073 4.01
0.017 3.63 0.064 3.66 0.058 4.02
200
0.025 4.16
200
0.014 4.18
400
0.017 4.21
0.014 4.16 0.013 4.18 0.038 4.35
0.020 4.15 0.019 4.16 0.023 4.42
Table-4.3: Joining of two random networks with equal number of nodes
50-50,
100-100,
200-200
Figure-4.5: Probability Vs Clustering coefficient for joint network formed by joining two
random networks with equal number of nodes
Based on degree Based on CC Based on APL
41
50-50,
100-100,
200-200
Figure-4.6: Probability Vs Average path length for joint network formed by joining two
random networks with equal number of nodes
Table-4.4 shows the properties of the individual networks with unequal number of
nodes and joint network formed by joining random networks with unequal number of
nodes.
Random network1 Random network2 Joint Network (P)
N1 Avg_cus Avg_apl N2 Avg_cus Avg_apl N Avg_cus Avg_apl
50
0.072 3.34
100
0.020 3.61
150
0.041 3.36
0.062 3.12 0.077 3.65 0.092 3.48
0.030 3.09 0.010 3.59 0.039 3.52
50
0.117 3.10
200
0.027 4.17
250
0.037 3.54
0.054 3.01 0.025 4.2 0.077 3.58
0.042 3.02 0.017 4.16 0.058 3.62
Based on degree Based on CC Based on APL
42
100
0.043 3.65
200
0.015 4.16
300
0.027 3.79
0.039 3.61 0.018 4.12 0.044 3.78
0.011 3.52 0.027 4.17 0.043 3.77
50-100,
50-200,
100-200
Figure-4.7: Probability Vs Clustering coefficient for joint network formed by joining two
random networks with unequal number of nodes
Table-4.4: Joining of two random networks with unequal number of nodes
Based on degree Based on CC Based on APL
43
50-100,
50-200,
100-200
Figure-4.8: Probability Vs Average path length for joint network formed by joining two
random networks with unequal number of nodes
The clustering coefficient of the resultant joint network formed by joining two
random networks with equal number of nodes increases as the probability increases and
the average path length of the joint network decreases as the probability increases. These
results are same for the joint network formed by joining two random networks with
unequal number of nodes. In both cases the properties of the joint network are similar to
the properties of small world model.
Joining small world network and random network
The different scenarios that we consider here are: 1) A small world network and a
random network with equal number of nodes, and 2) A small world and a random
network with unequal number of nodes.
Based on degree Based on CC Based on APL
44
Table-4.5 shows the properties of the individual networks with equal number of nodes
and also joint network formed by joining a small world network and a random network
with equal number of nodes.
Small world network Random network Joint Network (P)
N1 Avg_cus Avg_apl N2 Avg_cus Avg_apl N Avg_cus Avg_apl
50 0.273 3.41 50 0.126 3.04 100 0.116 3.40
0.146 3.03 0.081 3.07 0.110 3.21
0.128 3.12 0.048 3.07 0.176 3.49
100 0.286 4.19 100 0.019 3.59 200 0.080 3.71
0.125 3.77 0.030 3.60 0.134 3.69
0.181 4.01 0.068 3.68 0.093 3.94
200 0.285 5.44 200 0.017 4.24 400 0.039 4.06
0.165 4.55 0.029 4.18 0.056 4.27
0.122 4.52 0.006 4.22 0.065 4.42
Table-4.5: Joining of a SWN and a random network with equal number of nodes
45
50-50,
100-100,
200-200
Figure-4.9: Probability Vs Clustering coefficient for joint network formed by joining a
small world network and a random network with equal number of nodes
50-50,
100-100,
200-200
Figure-4.10: Probability Vs Average path length for joint network formed by joining a
small world network and a random network with equal number of nodes
Table-4.6 shows the properties of the individual networks with unequal number of
nodes and joint network formed by joining a small world network and a random network
with unequal number of nodes.
Based on degree Based on CC Based on APL
Based on degree Based on CC Based on APL
46
Small world network Random network Joint Network (P)
N1 Avg_cus Avg_apl N2 Avg_cus Avg_apl N Avg_cus Avg_apl
50
0.290 3.36
100
0.032 3.65
150
0.086 3.29
0.212 3.35 0.033 3.60 0.072 3.32
0.215 3.46 0.044 3.61 0.076 3.51
50
0.294 3.44
200
0.009 4.17
250
0.060 3.56
0.180 3.30 0.011 4.12 0.088 3.42
0.178 3.13 0.023 4.14 0.046 3.67
100
0.301 4.57
200
0.017 4.22
300
0.066 3.70
0.167 3.88 0.019 4.24 0.057 3.96
0.147 3.94 0.020 4.13 0.085 3.83
100
0.291 4.74
50
0.069 3.07
150
0.137 3.13
0.111 3.83 0.085 3.13 0.199 3.08
0.088 3.68 0.018 3.08 0.127 3.61
200
0.294 5.24
50
0.040 3.01
250
0.160 3.26
0.079 4.35 0.091 3.09 0.091 3.71
0.131 4.41 0.071 3.05 0.139 3.54
200
0.251 4.96
100
0.044 3.63
300
0.124 3.70
0.121 4.49 0.065 3.63 0.137 3.78
0.147 4.50 0.050 3.60 0.092 4.06
Table-4.6: Joining of a SWN and a random network with unequal number of nodes
47
50-200,
100-200,
200-50, 50-100, 200-100, 100-50
Figure-4.11: Probability Vs Clustering coefficient for joint network formed by joining a
small world network and a random network with unequal number of nodes
100-200,
100-50,
200-50, 200-100, 50-200, 50-100
Figure-4.12: Probability Vs Average path length for joint network formed by joining a
small world network and a random network with unequal number of nodes
Based on degree Based on CC Based on APL
Based on degree Based on CC Based on APL
48
As we can see from the above graphs the clustering coefficient of the resultant joint
network formed by joining a small world network and a random network with equal
number of nodes decreases initially and then increases as the probability increases. The
average path length of the joint network decreases gradually as the probability increases.
The results are same for the joint network formed by joining a small world network and a
random network with unequal number of nodes.
49
GROWING AN EXISTING SMALL WORLD NETWORK
Initially we generate a small world network and then we grow that network by
adding one node at each step until the network is grown to a desired size. While growing
a network we consider the structural aspects such as connecting to a well established
node and communities. The properties of the network as it is grown are shown in the
form of graphs. In these graphs, networks with N number of nodes are grown until
networks reaches N+100 number of nodes.
50, 100, 150, 200
Figure-4.13: Nodes being added Vs Clustering coefficient for a growing SW network
Based on degree
Based on CC
Based on APL
50
50, 100, 150, 200
Figure-4.14: Nodes being added Vs Average path length for a growing SW network
The average clustering coefficient of the growing small world network is better
than that of the small world network considered initially. As the number of nodes in the
starting network increases, the growth in the clustering coefficient with respect to the
number of nodes being added is reduced. The average path length of the growing network
is almost similar to the initial small world networks. Based on the above observations we
could say that growth of the small world network using the proposed model will preserve
the characteristics of the network considered.
Based on degree Based on CC Based on APL
51
OTHER LATTCIE STRUCTURES
SQUARE ALTTICE
Here a square lattice is initially considered. Based on a probability P every edge
in the square lattice is rewired. The properties such as clustering coefficient and average
path length of the square lattice structure with 25 nodes (5 rows, 5 columns) and 100
nodes (10 rows, 10 columns) after rewiring with a probability P are shown below.
Figure-4.15: Probability Vs Clustering coefficient for a rewired square lattice structure
with 25 nodes and 100 nodes.
52
Figure-4.16: Probability Vs Average path length for a rewired square lattice structure
with 25 nodes and 100 nodes.
Form the above graphs we can see the clustering coefficient of the square lattice is 0
initially. As the rewiring probability increases it is possible that the clustering coefficient
of the rewired structure increases for certain probability values and behaves like a small
world. As the number of nodes of the square structure increases, the range of variation in
the clustering coefficient decreases. Average path length of the rewired square lattice is
much better than that of regular square lattice and the amount of decrease in the average
path length increases as the number of nodes in the square structure increases. Hence we
can say that the rewired square structure behaves like a small world network for certain
probabilities and like a random network for other probability values.
53
HEXAGONAL LATTICE
Here a hexagonal lattice structure is initially considered. Based on probability P
every edge in this structure is rewired. The properties such as clustering coefficient and
average path length for two layers of hexagons and three layers of hexagons after
rewiring with a probability P are shown below:
Figure-4.17: Probability Vs Clustering coefficient for a rewired two layered and three
layered hexagonal lattice structure.
54
Figure-4.18: Probability Vs Average path length for a rewired two layered and three
layered hexagonal lattice structure.
The clustering coefficient of the hexagonal lattice starts from 0 and increases for
certain probability values. As the number of nodes increases, the variation in the
clustering coefficient decreases. Average path length of the rewired hexagonal lattice is
little better than that of regular hexagonal structure, since the hexagonal structure has a
better average path length initially.
55
CHAPTER 5
CONCLUSION
We have simulated a joint network by joining different networks, namely small
world- small world, small world-random and random-random. We joined these networks
based on the structural properties such as members in one network get connected to the
members in other network where there is active communication between the members, to
members who has large number of connections in the network and to members from
where it is easy to meet new friends or old friends. We have provided simulated results
for the above cases. These results show that most of the joint networks simulated using
proposed approach behaves like small world networks in terms of clustering coefficient
and average path length.
We also proposed a model for growing an existing small world network. In this
also we considered structural issues. When a new node is connected to a few existing
nodes in a network, internal evolution in the network takes place based on the linear
function probability. The results of these simulations show that network grown using the
proposed model have better properties that that of the initially considered small world
network.
Finally, we have worked on rewiring square and hexagonal lattice structures and
studied the properties like clustering coefficient and average path length.
56
BIBLIOGRAPHY
1) Erdos, P and Renyi, A. Random graphs, Math’s Review, pp.290-297, 1959.
2) Erd_s, P.; Rényi, A. On random graphs. I. Publicationes Mathematicae 6: 290–
297,1959.
3) Barabasi, A-L and Albert, R. Emergence of scaling in random networks, Science,
pp.509-512, 1999.
4) Barabasi, A-L. Linked, The New Science of Networks. Cambridge,Perseus, 2002.
5) Duncan J. Watts, “Small worlds: the dynamics of networks between order and
randomness”. Princeton University Press, 2003.
6) Watts, The new science of networks. Ann-Rev of Sociology 30, 243-270, 2004.
7) Mark E. J. Newman, Albert-László Barabási, Duncan J. Watts, “The structure and
dynamics of networks”. Princeton University Press, 2006.
8) Stanley Milgram, “The Small World Problem”, Psychology Today, pp.60-
67,1967
9) Sandeep Chalasani, “On the Value of a Social Network”, arXiv:0812.2891.
10)Watts, D and Strogatz, S. Collective dynamics of small world networks, Nature,
pp. 440-442, 1998.
57
11)Ozik, B.-R. Hunt, E. Ott, “Growing networks with geographical attachment
preference: Emergence of small worlds”, Phys. Rev. E 69 (2004) 026108.
12) Z.Z. Zhang, L.L. Rong, C.H. Guo, “A deterministic small world network created
by edge iteration”, Physica A 363 (2006) 567.
13) Z.Z. Zhang, L.L. Rong, F. Comellas, “Evolving Small world networks with
geographical attachment preference”, J. Phys. A 39 (2006) 3253.
14) Zhong-zhi Zhang, Shuigeng Zhou, Zhen Shen, Jihong Guanc, “From regular to
growing small-world networks”, Physica A 385 (2007) 765–772.
15) Li Yong, Fang Jin-Qing, Liu Qiang, and Liang Yong, “Small world properties
generated by new algorithm under same degree of all nodes”, Commun. Theor.
Phys. 45 (2006) pp. 950–954.
16) Xiao Fan Wang, Guanrang Chen, “Complex networks: small-world, scale-free
and beyond”, Circuits and Systems Magazine, IEEE, Vol 3 (2003) 6-20.
17) P. Erdös and A. Rényi, “On the evolution of random graphs”, Publ.Math. Inst.
Hung. Acad. Sci., vol. 5, pp. 17-60, 1959.
VITA
Suresh Babu Thippireddy
Candidate for the Degree of
Master of Science
Thesis: MODELS FOR EVOLUTION AND JOINING OF SMALL WORLD
NETWORKS
Major Field: Computer Science
Biographical:
Personal Data:
Born on August, 07, 1985
Education:
Completed the requirements for the Master of Science in Computer Science at
Oklahoma State University, Stillwater, Oklahoma in December, 2009.
Bachelor of Technology in Computer Science and Engineering at Jawaharlal
Nehru Technological University, Hyderabad, India.
Experience:
• Intern- Programmer, Community Care of Oklahoma, Tulsa, Oklahoma
• Research Assistant, Computer Science, Oklahoma State University
• Research Assistant, Mechanical and Aerospace Engineering, Oklahoma
State University,
• Teaching Assistant, Computer Science, Oklahoma State University
• Intern – Institute of Electronic Governance, Hyderabad, India
Professional Memberships:
• Member of Golden Key International Honor Society, Oklahoma State
University - 2009
ADVISER’S APPROVAL: Dr. Subhash Kak
Name: Suresh Babu Thippireddy Date of Degree: December, 2009
Institution: Oklahoma State University Location: Stillwater, Oklahoma
Title of Study: MODELS FOR EVOLUTION AND JOINING OF SMALL WORLD
NETWORKS
Pages in Study: 57 Candidate for the Degree of Master of Science
Major Field: Computer Science
Scope and Method of Study: Social networks are characterized by various properties
related to clustering of nodes and the degree of separation amongst nodes. The
small world network model of Watts-Strogatz model begins with a regular lattice
and converts it to a random graph using a rewiring procedure. Evolving small
world networks have not been much studied in the literature. Here we study real
world networks in which a group of nodes initially join to form the network and
then get attached to an existing small world network. The main objective of this
work is to study the joining of two existing networks and the growing of a
network based on certain structural aspects like connecting to a well established
member of a network, connecting to active communities in a network and finding
new/old friends in a network. We also investigate the properties of the network
formed by rewiring square and hexagonal lattice structures.
Findings and Conclusions: We have simulated joining of different combinations networks
like small world-small world, random-random and small world-random networks
and observed that the properties of joint network to be similar to that of small
world networks. We have also simulated the growth of an existing small world
network and have seen the properties of growing network to be similar to small
world networks. We have also studied the properties of the networks generated by
rewiring the square and hexagonal lattice structures.