{"id":9314,"date":"2016-07-14T06:16:18","date_gmt":"2016-07-14T06:16:18","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=9314"},"modified":"2016-07-14T06:16:18","modified_gmt":"2016-07-14T06:16:18","slug":"exploring-networks-efficiently","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/exploring-networks-efficiently\/","title":{"rendered":"Exploring networks efficiently"},"content":{"rendered":"

Analysis of ant colony behavior could yield better algorithms for network communication.<\/strong><\/em><\/span><\/p>\n

\"\u201cIt\u2019s<\/a>
\u201cIt\u2019s intuitive that if a bunch of people are randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density,\u201d says Cameron Musco, an MIT graduate student in electrical engineering and computer science. \u201cWhat we\u2019re doing is giving a rigorous analysis behind that intuition, and also saying that the estimate is a very good estimate, rather than some coarse estimate.\u201d
Illustration: Christine Daniloff\/MIT<\/figcaption><\/figure>\n

CAMBRIDGE, Mass.<\/strong> —\u00a0Ants, it turns out, are extremely good at estimating the concentration of other ants in their vicinity. This ability appears to play a role in several communal activities, particularly in the voting procedure whereby an ant colony selects a new nest.<\/span><\/p>\n

Biologists have long suspected that ants base their population-density estimates on the frequency with which they \u2014 literally \u2014 bump into other ants while randomly exploring their environments.<\/span><\/p>\n

That theory gets new support from a theoretical paper that researchers from MIT\u2019s Computer Science and Artificial Intelligence Laboratory will present at the Association for Computing Machinery\u2019s Symposium on Principles of Distributed Computing conference later this month. The paper shows that observations from random exploration of the environment converge very quickly on an accurate estimate of population density. Indeed, they converge about as quickly as is theoretically possible.<\/span><\/p>\n

[pullquote]The grid that the researchers used to model the ants\u2019 environment is just a special instance of a data structure called a graph.[\/pullquote]<\/p>\n

Beyond offering support for biologists\u2019 suppositions, this theoretical framework also applies to the analysis of social networks, of collective decision making among robot swarms, and of communication in<\/span>\u00a0ad hoc networks<\/a>, such as networks of low-cost sensors scattered in forbidding environments.<\/span><\/p>\n

\u201cIt\u2019s intuitive that if a bunch of people are randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density,\u201d says Cameron Musco, an MIT graduate student in electrical engineering and computer science and a co-author on the new paper. \u201cWhat we\u2019re doing is giving a rigorous analysis behind that intuition, and also saying that the estimate is a very good estimate, rather than some coarse estimate. As a function of time, it gets more and more accurate, and it goes nearly as fast as you would expect you could ever do.\u201d<\/span><\/p>\n

Random walks<\/strong><\/span><\/p>\n

Musco and his coauthors \u2014 his advisor, NEC Professor of Software Science and Engineering Nancy Lynch, and Hsin-Hao Su, a postdoc in Lynch\u2019s group \u2014 characterize an ant\u2019s environment as a grid, with some number of other ants scattered randomly across it. The ant of interest \u2014 call it the explorer \u2014 starts at some cell of the grid and, with equal probability, moves to one of the adjacent cells. Then, with equal probability, it moves to one of the cells adjacent to that one, and so on. In statistics, this is referred to as a \u201crandom walk.\u201d The explorer counts the number of other ants inhabiting every cell it visits.<\/span><\/p>\n

In their paper, the researchers compare the random walk to random sampling, in which cells are selected from the grid at random and the number of ants counted. The accuracy of both approaches improves with each additional sample, but remarkably, the random walk converges on the true population density virtually as quickly as random sampling does.<\/span><\/p>\n

That\u2019s important because in many practical cases, random sampling isn\u2019t an option. Suppose, for instance, that you want to write an algorithm to analyze an online social network \u2014 say, to estimate what fraction of the network self-describes as Republican. There\u2019s no publicly available list of the network\u2019s members; the only way to explore it is to pick an individual member and start tracing connections.<\/span><\/p>\n

Similarly, in ad hoc networks, a given device knows only the locations of the devices in its immediate vicinity; it doesn\u2019t know the layout of the network as a whole. An algorithm that uses random walks to aggregate information from multiple devices would be much easier to implement than one that has to characterize the network as a whole.<\/span><\/p>\n

Repeat encounters<\/strong><\/span><\/p>\n

The researchers\u2019 result is surprising because, at every step of a random walk, the explorer has a significant likelihood of returning to a cell that it has already visited. An estimate derived from random walks thus has a much higher chance of oversampling particular cells than one based on random sampling does.<\/span><\/p>\n

Initially, Musco says, he and his colleagues assumed that this was a liability that an algorithm for estimating population density would have to overcome. But their attempts to filter out oversampled data seemed to worsen their algorithm\u2019s performance rather than improve it. Ultimately, the were able to explain why, theoretically.<\/span><\/p>\n

\u201cIf you\u2019re randomly walking around a grid, you\u2019re not going to bump into everybody, because you\u2019re not going to cross the whole grid,\u201d Musco says. \u201cSo there\u2019s somebody on the far side of the grid that I have pretty much a zero percent chance of bumping into. But while I\u2019ll bump into those guys less, I\u2019ll bump into local guys more. I need to count all my interactions with the local guys to make up for the fact that there are these faraway guys that I\u2019m never going to bump into. It sort of perfectly balances out. It\u2019s really easy to prove that, but it\u2019s not very intuitive, so it took us a while to realize this.\u201d<\/span><\/p>\n

Generalizations<\/strong><\/span><\/p>\n

The grid that the researchers used to model the ants\u2019 environment is just a special instance of a data structure called a graph. A graph consists of nodes, typically represented by circles, and edges, typically represented as line segments connecting nodes. In the grid, each cell is a node, and it shares edges only with those cells immediately adjacent to it.<\/span><\/p>\n

The researchers\u2019 analytic techniques, however, apply to any graph, such as one describing which members of a social network are connected, or which devices in an ad hoc network are within communication range of each other.<\/span><\/p>\n

If the graph is not very well connected \u2014 if, for instance, it\u2019s just a chain of nodes, each connected only to the two nodes adjacent to it \u2014 then oversampling can become a problem. In a chain of, say, 100 nodes, an explorer taking a random walk could get stuck traversing the same five or six nodes over and over again.<\/span><\/p>\n

But as long as two random walks starting from the same node are likely to branch out in different directions, as is often the case in graphs describing communication networks, random walks remain virtually as good as random sampling.<\/span><\/p>\n

Moreover, in the new paper, the researchers analyze random walks executed by a single explorer. Pooling observations from many explorers would converge on an accurate estimate more quickly. \u201cIf they were robots instead of ants, they could get gains by talking to each other and saying, \u2018Oh, this is my estimate,\u2019\u201d Musco says.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Researchers from MIT\u2019s Computer Science and Artificial Intelligence Laboratory will present at the Association for Computing Machinery\u2019s Symposium on Principles of Distributed Computing conference later this month.<\/p>\n","protected":false},"author":6,"featured_media":9315,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[],"class_list":["post-9314","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2016\/07\/MIT-Random-Walks_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/9314","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=9314"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/9314\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/9315"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=9314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=9314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=9314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}