UW's Small world Applications & Theory Team
(SWAT team, for short) consists of a group of undergraduate and graduate
students from various discplines, and meets weekly under the supervision
of Bryan Shader.The goal of the SWAT team is to scientifically investigate
various small-world phenomena.Familiar examples of small-world phenomena
are
- the interconnectedness of the WWW--it is possible to get from any
webpage to another in at most 18 links,
- the fast spread of viruses across the world--that is greatly quickened
by international travel,
- the Kevin Bacon Game--the goal is to start with a random actor and
then find a sequence of actors from the random actor to Kevin
Bacon with the property that any two consecutive actors were in a common
movie,
- the airplane phenomena--why is it that the person seated next to
you on the airplane always knows someone who knows someone .... who
knows your Aunt Ruth?
Less familiar examples of small-world phenomena are:
- the efficiency, and vulnerabilty of the U.S.'s power grid,
- the neural network of different animals,
- the synchronized flashing of fireflys in Papua New Guinea, and
- the structure of river and tributary drainage basins.
The goal of the SWAT team is to find research projects
for each member to work on. Research projects are designed to fit members'
strength and can be individual or group projects. Once a project is determined
there are numerous opportunities for supporting undergraduate research,
and the team and supervise will provide the necessary encouragement and advise
to pursue these funding opportunities. What could be better than getting
paid to explore!
If you are interested in joining the SWAT team, contact Bryan Shader via
e-mail at bshader@uwyo.edu or drop by his office at RH 321.
Past projects:
Project:
Robustness of Small-world networks
Student:
Andy Curtis
Funding: EPSCoR
Undergraduate Research Scholarship Fall 2003 & Spring 2004
Publications:
Andy
Curtis,
Small-worlds: Beyond Social Networking,
Rose-Hulman Undergraduate Math Journal, Article 7, 2004.
download
article at
http://www.rose-hulman.edu/mathjournal/download.html
Abstract:
Small-world phenomena were initially studied in the 1960s
through a series of social network experiments, and are, as evidenced by
the game "The six degrees of Kevin Bacon", even part of our pop-culture.
Recently, mathematicians and physicists have shown that most small-world
phenomena are expected consequences of the mathematical properties of certain
networks--known as {\em small-world networks}. In this paper, we survey some
recent mathematical developments dealing with small-world networks, as
well as present a new small-world network model and discuss some new ideas
for decentralized searching. The goal is to give the reader a sense of the
importance of small-world networks, and some of the useful applications
dealing with these networks.
Project:
External memory algorithms for graphs and digraphs
Student:
Andy Curtis
Funding: Wyoming
NASA Space Grant, Summer 2004
Publications:
Andy Curtis and B. Shader,
Testing acyclicity and topological
sort
in external memory, under review.
Abstract There has
been a considerable amount of work recently to develop external-memory algorithms
for fundamental graph algorithms. This is due the increasing size of data
sets for many modern applications. In external-memory algorithm design, memory
is managed as part of the algorithm to minimize the number of input/outputs
(I/Os) performed between internal memory and secondary storage. The number
of operations performed by the CPU is generally ignored in external algorithm
analysis, since a typical transfer of data from disk is about one million
times slower than from internal memory. For a recent surveys, see [11, 12].
In this paper, we present the first I/O efficient algorithm to determine
if a general directed graph is acyclic. In addition to checking acyclicity
our algorithm returns a topological ordering of the vertices. I/O efficient
topological sorting has been a long-standing open problem, and our results
help to further progress work on this problem. Our acyclicity testing algorithm
has an I/Ocomplexity of O((V + E B)log2(VB)+ sort(E)). Note that this bound
matches the best known bound for topological sorting a general digraph using
DFS. While our results don’t beat the previously known algorithm of [7],
we provide further insight into the external-memory topological sorting problems.
Current projects:
Project:
Coin weighing problems
Student:
Kim Creaser
Funding: EPSCOR
undergraduate research scholarship, pending
Project:
Electronic voting and cryptography
Student:
Brenda Christensen
Funding:
EPSCOR undergraduate research scholarship, pending
Back to Bryan Shader's
homepage
Back to Math Department
homepage