Seminar with Larry Wen
Title: Scale-free Networks, Algorithms and Complex
Software Systems
Speaker: Larry Wen, PhD Student, Griffith University
Place: Room 78-621, GP South.
Time: Thursday 24th March, 11:00am
Abstract:
The Scale-free network is a network model that has become prominent in
recent years. Compared to the traditional random network model, the most
prominent feature of a scale-free network is that a few nodes (called hubs)
dominate other nodes by having a much larger number of links. Also, the tail
of the degree distribution follows a power law. Many large complex networks
have been found to be scale-free, including the WWW, and power grids.
In our research, we have studied the topological structure of two different
types of networks. The first is called a class (or component) dependency
network (CDN) and the second is called sorting comparison network (SCN). We
have found that the scale-free property exists in both types of networks.
Large software systems are usually composed of many components or classes.
To make a software system function properly, individual classes, even with
their own functionalities, must cooperate with others to function properly.
In other words, nearly every class (or component) depends on the existence
or collaboration of other classes. If we draw classes as nodes and the
dependent relationship as links, we will have a dependency network and call
it CDN. Results will be given for a large java library.
Most sorting algorithms require the comparison of the key values of target
records. If we consider a record as a node and the comparison between two
records as a link, the process to sort a sequence of records generates a
comparison network. We call this network as SCN (sorting comparison
network). In our research, we've found for efficient sorting algorithm (we
define the efficiency as the number of comparisons), the SCN is tend to be
scale-free.
Our discovery of the scale-free property in CDN and SCN not only adds two
names to the already very long list of scale-free networks, but also
provides new approaches to study the evolution and optimization of the
architecture of large complex software systems. The SCN is quite different
from traditional scale-free networks. For most well known scale-free
networks the evolutionary processes are stochastic and the weaving of the
networks seems to be random. This means the exact result can't be repeated
by another similar network. However, for a SCN, once the sorting algorithm
and the sequence are given, the process of the network evolution is
determined. Therefore, the SCN provides a more determinable and more
repeatable approach for studying scale-free networks. There is also an
important link between the scale-free property and the optimality of the
particular type of algorithm
Speaker: Larry Wen, PhD Student, Griffith University
Place: Room 78-621, GP South.
Time: Thursday 24th March, 11:00am
Abstract:
The Scale-free network is a network model that has become prominent in
recent years. Compared to the traditional random network model, the most
prominent feature of a scale-free network is that a few nodes (called hubs)
dominate other nodes by having a much larger number of links. Also, the tail
of the degree distribution follows a power law. Many large complex networks
have been found to be scale-free, including the WWW, and power grids.
In our research, we have studied the topological structure of two different
types of networks. The first is called a class (or component) dependency
network (CDN) and the second is called sorting comparison network (SCN). We
have found that the scale-free property exists in both types of networks.
Large software systems are usually composed of many components or classes.
To make a software system function properly, individual classes, even with
their own functionalities, must cooperate with others to function properly.
In other words, nearly every class (or component) depends on the existence
or collaboration of other classes. If we draw classes as nodes and the
dependent relationship as links, we will have a dependency network and call
it CDN. Results will be given for a large java library.
Most sorting algorithms require the comparison of the key values of target
records. If we consider a record as a node and the comparison between two
records as a link, the process to sort a sequence of records generates a
comparison network. We call this network as SCN (sorting comparison
network). In our research, we've found for efficient sorting algorithm (we
define the efficiency as the number of comparisons), the SCN is tend to be
scale-free.
Our discovery of the scale-free property in CDN and SCN not only adds two
names to the already very long list of scale-free networks, but also
provides new approaches to study the evolution and optimization of the
architecture of large complex software systems. The SCN is quite different
from traditional scale-free networks. For most well known scale-free
networks the evolutionary processes are stochastic and the weaving of the
networks seems to be random. This means the exact result can't be repeated
by another similar network. However, for a SCN, once the sorting algorithm
and the sequence are given, the process of the network evolution is
determined. Therefore, the SCN provides a more determinable and more
repeatable approach for studying scale-free networks. There is also an
important link between the scale-free property and the optimality of the
particular type of algorithm
