Publications Search
Marc Maier, Matthew Rattigan, David Jensen
Indexing Network Structure with Shortest-Path Trees Journal Article
In: ACM Trans. Knowl. Discov. Data, vol. 5, no. 3, 2011, ISSN: 1556-4681.
Abstract | Links | BibTeX | Tags: Navigation and Routing in Networks
@article{10.1145/1993077.1993079,
title = {Indexing Network Structure with Shortest-Path Trees},
author = {Marc Maier and Matthew Rattigan and David Jensen},
url = {https://doi.org/10.1145/1993077.1993079},
doi = {10.1145/1993077.1993079},
issn = {1556-4681},
year = {2011},
date = {2011-08-01},
journal = {ACM Trans. Knowl. Discov. Data},
volume = {5},
number = {3},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
abstract = {The ability to discover low-cost paths in networks has practical consequences for knowledge discovery and social network analysis tasks. Many analytic techniques for networks require finding low-cost paths, but exact methods for search become prohibitive for large networks, and data sets are steadily increasing in size. Short paths can be found efficiently by utilizing an index of network structure, which estimates network distances and enables rapid discovery of short paths. Through experiments on synthetic networks, we demonstrate that one such novel network structure index based on the shortest-path tree outperforms other previously proposed indices. We also show that it generalizes across arbitrarily weighted networks of various structures and densities, provides accurate estimates of distance, and has efficient time and space complexity. We present results on real data sets for several applications, including navigation, diameter estimation, centrality computation, and clustering---all made efficient by virtue of the network structure index.},
keywords = {Navigation and Routing in Networks},
pubstate = {published},
tppubtype = {article}
}
The ability to discover low-cost paths in networks has practical consequences for knowledge discovery and social network analysis tasks. Many analytic techniques for networks require finding low-cost paths, but exact methods for search become prohibitive for large networks, and data sets are steadily increasing in size. Short paths can be found efficiently by utilizing an index of network structure, which estimates network distances and enables rapid discovery of short paths. Through experiments on synthetic networks, we demonstrate that one such novel network structure index based on the shortest-path tree outperforms other previously proposed indices. We also show that it generalizes across arbitrarily weighted networks of various structures and densities, provides accurate estimates of distance, and has efficient time and space complexity. We present results on real data sets for several applications, including navigation, diameter estimation, centrality computation, and clustering---all made efficient by virtue of the network structure index.
Ozgur Simsek, David Jensen
Navigating networks by using homophily and degree Journal Article
In: Proceedings of the National Academy of Sciences, vol. 105, no. 35, pp. 12758–12762, 2008.
Abstract | Links | BibTeX | Tags: Navigation and Routing in Networks
@article{csimcsek2008navigating,
title = {Navigating networks by using homophily and degree},
author = {Ozgur Simsek and David Jensen},
url = {https://www.pnas.org/content/pnas/105/35/12758.full.pdf},
year = {2008},
date = {2008-01-01},
journal = {Proceedings of the National Academy of Sciences},
volume = {105},
number = {35},
pages = {12758--12762},
publisher = {National Academy of Sciences},
abstract = {Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.},
keywords = {Navigation and Routing in Networks},
pubstate = {published},
tppubtype = {article}
}
Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.
John Burgess, Brian Gallagher, David Jensen, Brian Neil Levine
MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks Proceedings Article
In: INFOCOM 2006. 25th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain, IEEE, 2006.
Abstract | Links | BibTeX | Tags: Navigation and Routing in Networks
@inproceedings{DBLP:conf/infocom/BurgessGJL06,
title = {MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks},
author = {John Burgess and Brian Gallagher and David Jensen and Brian Neil Levine},
url = {https://doi.org/10.1109/INFOCOM.2006.228},
doi = {10.1109/INFOCOM.2006.228},
year = {2006},
date = {2006-01-01},
booktitle = {INFOCOM 2006. 25th IEEE International Conference on Computer Communications,
Joint Conference of the IEEE Computer and Communications Societies,
23-29 April 2006, Barcelona, Catalunya, Spain},
publisher = {IEEE},
abstract = {Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments.},
keywords = {Navigation and Routing in Networks},
pubstate = {published},
tppubtype = {inproceedings}
}
Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments.
Matthew Rattigan, Marc Maier, David Jensen
Using structure indices for efficient approximation of network properties Proceedings Article
In: Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August 20-23, 2006, pp. 357–366, ACM, 2006.
Abstract | Links | BibTeX | Tags: Navigation and Routing in Networks
@inproceedings{DBLP:conf/kdd/RattiganMJ06,
title = {Using structure indices for efficient approximation of network properties},
author = {Matthew Rattigan and Marc Maier and David Jensen},
url = {https://doi.org/10.1145/1150402.1150443},
doi = {10.1145/1150402.1150443},
year = {2006},
date = {2006-01-01},
booktitle = {Proceedings of the Twelfth ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August
20-23, 2006},
pages = {357--366},
publisher = {ACM},
abstract = {Statistics on networks have become vital to the study of relational data drawn from areas such as bibliometrics, fraud detection, bioinformatics, and the Internet. Calculating many of the most important measures - such as betweenness centrality, closeness centrality, and graph diameter-requires identifying short paths in these networks. However, finding these short paths can be intractable for even moderate-size networks. We introduce the concept of a network structure index (NSI), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. We present several varieties of NSIs, examine their time and space complexity, and analyze their performance on synthetic and real data sets. We show that creating an NSI for a given network enables extremely efficient and accurate estimation of a wide variety of network statistics on that network.},
keywords = {Navigation and Routing in Networks},
pubstate = {published},
tppubtype = {inproceedings}
}
Statistics on networks have become vital to the study of relational data drawn from areas such as bibliometrics, fraud detection, bioinformatics, and the Internet. Calculating many of the most important measures - such as betweenness centrality, closeness centrality, and graph diameter-requires identifying short paths in these networks. However, finding these short paths can be intractable for even moderate-size networks. We introduce the concept of a network structure index (NSI), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. We present several varieties of NSIs, examine their time and space complexity, and analyze their performance on synthetic and real data sets. We show that creating an NSI for a given network enables extremely efficient and accurate estimation of a wide variety of network statistics on that network.
Andrew Fast, David Jensen, Brian Neil Levine
Creating social networks to improve peer-to-peer networking Proceedings Article
In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Illinois, USA, August 21-24, 2005, pp. 568–573, ACM, 2005.
Abstract | Links | BibTeX | Tags: Navigation and Routing in Networks
@inproceedings{DBLP:conf/kdd/FastJL05,
title = {Creating social networks to improve peer-to-peer networking},
author = {Andrew Fast and David Jensen and Brian Neil Levine},
url = {https://doi.org/10.1145/1081870.1081938},
doi = {10.1145/1081870.1081938},
year = {2005},
date = {2005-01-01},
booktitle = {Proceedings of the Eleventh ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, Chicago, Illinois, USA, August
21-24, 2005},
pages = {568--573},
publisher = {ACM},
abstract = {We use knowledge discovery techniques to guide the creation of efficient overlay networks for peer-to-peer file sharing. An overlay network specifies the logical connections among peers in a network and is distinct from the physical connections of the network. It determines the order in which peers will be queried when a user is searching for a specific file. To better understand the role of the network overlay structure in the performance of peer-to-peer file sharing protocols, we compare several methods for creating overlay networks. We analyze the networks using data from a campus network for peer-to-peer file sharing that recorded anonymized data on 6,528 users sharing 291,925 music files over an 81-day period. We propose a novel protocol for overlay creation based on a model of user preference identified by latent-variable clustering with hierarchical Dirichlet processes (HDPs). Our simulations and empirical studies show that the clusters of songs created by HDPs effectively model user behavior and can be used to create desirable network overlays that outperform alternative approaches.},
keywords = {Navigation and Routing in Networks},
pubstate = {published},
tppubtype = {inproceedings}
}
We use knowledge discovery techniques to guide the creation of efficient overlay networks for peer-to-peer file sharing. An overlay network specifies the logical connections among peers in a network and is distinct from the physical connections of the network. It determines the order in which peers will be queried when a user is searching for a specific file. To better understand the role of the network overlay structure in the performance of peer-to-peer file sharing protocols, we compare several methods for creating overlay networks. We analyze the networks using data from a campus network for peer-to-peer file sharing that recorded anonymized data on 6,528 users sharing 291,925 music files over an 81-day period. We propose a novel protocol for overlay creation based on a model of user preference identified by latent-variable clustering with hierarchical Dirichlet processes (HDPs). Our simulations and empirical studies show that the clusters of songs created by HDPs effectively model user behavior and can be used to create desirable network overlays that outperform alternative approaches.