VAN K. NGUYEN
|
|
Ph.D. student, Algorithms and Theory Laboratory CS
Department , Phone: (530) 752-8819 - Fax: (530) 752-4767 Email: nguyenvk “at” cs.ucdavis.edu |
|
[Publications][Application Materials][Reading] [Links]
I am with Algorithms and Theory Laboratory in Computer Science Dept., UC-Davis. My advisor is Prof. Chip Martel.
I am very
proud of receiving the Best
Graduate Researcher Award of the Computer Science department at UC-Davis.
My research
interests includes:
§ Algorithms for networking and dist. computing: Network graphs & algorithms; Models for real-world large-scale networks; Small-world analysis
§ Networking: peer-to-peer; hybrid large-scale wireless networks; dynamic routing for optical wavelength division multiplexing (WDM) networks
§ Cryptography and Computer Security
Current Research
§ An algorithmic approach for large-scale dynamic networks
§ Learning from small-worlds: Efficient network designs with distance-bias links
Papers
§
Van Nguyen & Chip Martel, “Efficient Dynamic Routing Schemes in Euclidean Metrics”,
In preparation
§
Van Nguyen & Chip Martel, “Modeling small-worlds with
geographical factors: distance-bias & bounded-growth neighborhoods”,
2006, submitted.
§
Van Nguyen & Chip Martel, “Non-uniform Random Links in Small-world
Graphs: Models, Analysis and Applications in Network Designs”.
In internal review. To be submitted for journal publication. Abtract.
§ Van Nguyen & Chip Martel, “Designing Networks for Low Weight, Small Routing Diameter and Low Congestion”.
A shorten version to appear in INFOCOM’06. Abstract.
§
Van Nguyen &
§
§ Van Nguyen & Phil Rogaway, “PRF to OWF conversion when the key length equals the block length”, Technical Report, CS-UCDavis, 2002 – not publishable since problem already visited by an old paper, although we gave some good insight using modern techniques.
§
V.K. Nguyen & R. Saphavi-Naini, “On a
new model for electronic cash with the notion of anonymous mirror
wallets”, Tech. Report,
§ V.K. Nguyen & R. Saphavi-Naini, “A Framework for Combining Off-line & On-line Electronic Cash”, in Proc. of PAWEC’97, 1997.
Current
Research Projects
§ An algorithmic approach for large-scale dynamic networks (with Prof. Chip Martel).
The Small-world property, a surprising feature in many large-scale real-world networks including the Internet, has been modeled as a simple local-contact graph augmented by a selective non-uniform distribution of random links, by Watts & Strogatz, and Kleinberg (Nature, 1998 and 2000) - Background. We pursue a line of research on random structures of this type (and generalized), adding to the classical study of random graphs. We propose a new general model for small-world properties which also considers geographical factors and power-law degrees and a number of important follow-up results such as a thorough analysis of Kleinberg's small-world models (and many others). We also propose a general small-world construction framework, featuring a hierarchical family of random structures where short paths can be found using decentralized routing in more refined classes.
We focus on geographical factors, including the distance-bias tendency (links tend to favor closer distances) and the property of bounded growth in neighborhood expansion. Our refined model combines a growth bounded base graph with a distance-bias distribution of random links. We show when the small-world effect may occur and how the diameter changes depending on the coordination between the distance-bias parameter and the two bounded growth parameters. This helps explain why the Internet graph is considered as a small-world with low diameter, but is locally growth bounded. We develop analysis techniques for graphs with non-uniform random links, including a fractal-based analysis. Based on our analysis results, we develop routing algorithms to best exploit topological features, e.g. long-distance links (using our fractal-based analysis).
§ Learning from small-worlds: Efficient network designs with distance-bias links (with Prof. Chip Martel).
We design network topologies and routing strategies which optimize several measures simultaneously: low weight, small routing diameter, bounded degree and low congestion. In the context of computer networks, low weight means cheap cost for connecting cable (or bandwidth renting in building virtual private intranets); small diameter means limited hops in a path, and bounded degree means a bounded number of physical links connected to a node. This set of design issues is broader than traditional network design and hence, our work is useful and relevant to a set of traditional and emerging design problems such as in hybrid wireless networks and optical WDM networks.
Background
& Motivation
Four decades have gone since the first experiment (Milgram,
1967) which confirms a (probably,
centuries old) folklore that we are in a small-world where any two strangers
can be linked by a short chain of acquaintances. The recent extensive multi-disciplinary
research initiated by
Starting with
More background on real-world complex networks can be found in these reviews:
§ R. Albert and A.-L.Barabasi. Statistical mechanics of complex networks . Reviews of Modern Physics 74, 47 (2002).
§ S.N. Dorogovtsev and J.F.F. Mendes. Evolution of networks. Adv. Phys. 51, 1079-1187 (2002);
§
M. E. J. Newman. The
structure and function of complex networks.
§ J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proc. of the International Congress of Mathematicians (ICM), 2006 (to appear).
Application Materials
§ Research [Statement | Summary | Detailed Description ]
Real-World Random Networks
Some People
Workshops
Models of Real-World Random Networks
Program on Random Graphs and Large-Scale Real-World Networks - IMS
Theoretical Computer Science special
issue on Complex Networks
DIMACS Workshop on Complex Networks and their Applications
Courses and reading links
Milena Mihail’s Algorithms for Complex Networks
Jon Kleinberg’s The Structure of Information Networks
David Aldous’s From Random Graphs to Complex Networks
Jim Crutchfield’s Natural Computation and Self-Organization
Information Networks’ Reading List by Panayiotis Tsaparas
Algorithms
for Co mplex
Networks
CNLS Annual Conference on Networks
Some algorithms links
NIST, Dictionary of Algorithms and Data Structures.
Pierluigi Crescenzi, and Viggo Kann, “A compendium of NP optimization problems”
Steve Seiden's Theoretical Computer Science Cheat Sheet
Misc.
Berkeley Shuttle Bus Reservation
BBC – News, Sport news
Soccer News – Goal.com
My
daughter’s corner
Baby Ha-Vi (born March 03 to Momy
Chi & Dady Van)
|
|
|
|
|
with aunt
Hai-Nhu
|
with
Ha-Khiem-Bi
|
in Kim’s
Haircut
|
in Kim’s Haircut
|
