tag:blogger.com,1999:blog-212249942017-08-16T16:14:37.524-07:00Research BlogThe latest news from Research at GoogleGoogle Blogsnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-21224994.post-7492759680564894022017-04-03T10:00:00.000-07:002017-04-03T10:00:23.496-07:00Consistent Hashing with Bounded Loads<span class="byline-author">Posted by Vahab Mirrokni, Principal Scientist, Morteza Zadimoghaddam, Research Scientist, NYC Algorithms Team</span><br /><br />Running a large-scale web service, such as content hosting, necessarily requires <a href="https://en.wikipedia.org/wiki/Load_balancing_(computing)">load balancing</a> — distributing clients <i>uniformly</i> across multiple servers such that none get overloaded. Further, it is desirable to find an allocation that does not change very much over time in a <i>dynamic</i> environment in which both clients and servers can be added or removed at any time. In other words, we need the allocation of clients to servers to be <i>consistent</i> over time.<br /><br />In collaboration with <a href="http://www.diku.dk/~mthorup/">Mikkel Thorup</a>, a visiting researcher from university of Copenhagen, we developed a new efficient allocation algorithm for this problem with <i>tight guarantees</i> on the maximum load of each server, and studied it theoretically and empirically. We then worked with our Cloud team to implement it in <a href="https://cloud.google.com/pubsub/">Google Cloud Pub/Sub</a>, a scalable event streaming service, and observed substantial improvement on uniformity of the load allocation (in terms of the maximum load assigned to servers) while maintaining consistency and stability objectives. In August 2016 we described our algorithm in the paper “<a href="https://arxiv.org/abs/1608.01350">Consistent Hashing with Bounded Loads</a>”, and shared it on ArXiv for potential use by the broader research community. <br /><br />Three months later, Andrew Rodland from <a href="https://vimeo.com/">Vimeo</a> informed us that he had found the paper, implemented it in <a href="https://github.com/arodland/haproxy/commit/b02bed24daf64743cb9a571e93ed29ee4bc7efe7">haproxy</a> (a widely-used piece of open source software), and used it for their load balancing project at Vimeo. The results were dramatic: applying these algorithmic ideas helped them decrease the cache bandwidth by a factor of almost 8, eliminating a scaling bottleneck. He recently summarized this story in a <a href="https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed">blog post</a> detailing his use case. Needless to say, we were excited to learn that our theoretical research was not only put into application, but also that it was useful <i>and</i> open-sourced. <br /><br /><b>Background</b><br />While the concept of <a href="https://en.wikipedia.org/wiki/Consistent_hashing">consistent hashing</a> has been developed in the past to deal with load balancing in dynamic environments, a fundamental issue with all the previously developed schemes is that, in certain scenarios, they may result in sub-optimal load balancing on many servers. <br /><br />Additionally, both clients and servers may be added or removed periodically, and with such changes, we do not want to move too many clients. Thus, while the dynamic allocation algorithm has to always ensure a proper load balancing, it should also aim to minimize the number of clients moved after each change to the system. Such allocation problems become even more challenging when we face hard constraints on the capacity of each server - that is, each server has a capacity that the load may not exceed. Typically, we want capacities close to the average loads. <br /><br />In other words, we want to simultaneously achieve both <i>uniformity</i> and <i>consistency</i> in the resulting allocations. There is a vast amount of literature on solutions in the much simpler case where the set of servers is fixed and only the client set is updated, but in this post we discuss solutions that are relevant in the fully <i>dynamic</i> case where both clients and servers can be added and removed. <br /><br /><b>The Algorithm</b><br />We can think about the servers as bins and clients as balls to have a similar notation with well-studied <a href="https://en.wikipedia.org/wiki/Balls_into_bins">balls-to-bins stochastic processes</a>. The uniformity objective encourages all bins to have a load roughly equal to the average density (the number of balls divided by the number of bins). For some parameter ε, we set the capacity of each bin to either <a href="https://en.wikipedia.org/wiki/Floor_and_ceiling_functions">floor or ceiling</a> of the average load times (1+ε). This extra capacity allows us to design an allocation algorithm that meets the consistency objective in addition to the uniformity property. <br /><br />Imagine a given range of numbers overlaid on a circle. We apply a hash function to balls and a separate hash function to bins to obtain numbers in that range that correspond to positions on that circle. We then start allocating balls in a specific order independent of their hash values (let’s say based on their ID). Then each ball is moved clockwise and is assigned to the first bin with spare capacity. <br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-pgZ4b9H7VlM/WOJ91rDe_XI/AAAAAAAABqw/wIjtyPHheFgyHpXIqY4qNLhd_H9DnHsXACLcB/s1600/image00.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="588" src="https://3.bp.blogspot.com/-pgZ4b9H7VlM/WOJ91rDe_XI/AAAAAAAABqw/wIjtyPHheFgyHpXIqY4qNLhd_H9DnHsXACLcB/s640/image00.png" width="640" /></a></div>Consider the example above where 6 balls and 3 bins are assigned using two separate hash functions to random locations on the circle. For the sake of this instance, assume the capacity of each bin is set to 2. We start allocating balls in the increasing order of their ID values. Ball number 1 moves clockwise, and goes to bin C. Ball number 2 goes to A. Balls 3 and 4 go to bin B. Ball number 5 goes to bin C. Then ball number 6 moves clockwise and hits bin B first. However bin B has capacity 2 and already contains balls 3 and 4. So ball 6 keeps moving to reach bin C but that bin is also full. Finally, ball 6 ends up in bin A that has a spare slot for it.<br /><br />Upon any update in the system (ball or bin insertion/deletion), the allocation is recomputed to keep the uniformity objective. The art of the analysis is to show that a small update (a few number of insertions and deletions) results in minor changes in the state of the allocation and therefore the consistency objective is met. In <a href="https://arxiv.org/abs/1608.01350">our paper</a> we show that every ball removal or insertion in the system results in O(1/ε<sup>2</sup>) movements of other balls. The most important thing about this upper bound is that it is independent of the total number of balls or bins in the system. So if the number of balls or bins are doubled, this bound will not change. Having an upper bound independent of the number of balls or bins introduces room for scalability as the consistency objective is not violated if we move to bigger instances. Simulations for the number of movements (relocations) per update is shown below when an update occurs on a bin/server. <br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-IJFOHvSomXY/WOJ-AecmDaI/AAAAAAAABq0/wVAwJd8jxNs7cT30aU0ek3_WpPzYYSO9ACLcB/s1600/image01.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="505" src="https://3.bp.blogspot.com/-IJFOHvSomXY/WOJ-AecmDaI/AAAAAAAABq0/wVAwJd8jxNs7cT30aU0ek3_WpPzYYSO9ACLcB/s640/image01.png" width="640" /></a></div>The red curve shows the average number of movements and the blue bars indicate the variance for different values of ε (the x-axis). The dashed curve is the upper bound suggested by our theoretical results which fits nicely as a prediction of the actual number of movements. Furthermore, for any value of ε, we know the load of each bin is at most (1+ε) times the average load. Below we see the load distribution of bins for different values of ε=0.1, ε=0.3 and ε=0.9.<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-PUdBAM5bDKk/WOJ-Hm3HAgI/AAAAAAAABq4/iREEzcJjdIQ7YYYE6bfGIEsbQALIozEKgCLcB/s1600/image02.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="532" src="https://1.bp.blogspot.com/-PUdBAM5bDKk/WOJ-Hm3HAgI/AAAAAAAABq4/iREEzcJjdIQ7YYYE6bfGIEsbQALIozEKgCLcB/s640/image02.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">The distribution of loads for several values of ε. The load distribution is nearly uniform covering all ranges of loads from 0 to (1+ε) times average, and many bins with load equal to (1+ε) times average.</td></tr></tbody></table>As one can see there is a tradeoff — a lower ε helps with uniformity but not with consistency, while larger ε values help with consistency. A lower ε will ensure that many loads will be equal to the hard capacity limit of (1+ε) times the average, and the rest have a decaying distribution.<br /><br />When providing content hosting services, one must be ready to face a variety of instances with different characteristics. This consistent hashing scheme is ideal for such scenarios as it performs well even for worst-case instances. <br /><br />While our internal results are exciting, we are even more pleased that the broader community found our solution useful enough to <a href="https://github.com/arodland/haproxy">open-source</a>, allowing anyone to use this algorithm. If you are interested in further details of this research, please see the <a href="https://arxiv.org/abs/1608.01350">paper</a> on ArXiv, and stay tuned for more research from the <a href="https://research.google.com/teams/nycalg/">NYC Algorithms Team</a>!<br /><br /><b>Acknowledgements:</b><br />We would like to thank Alex Totok, Matt Gruskin, Sergey Kondratyev and Haakon Ringberg from the Google Cloud Pub/Sub team, and of course <a href="http://www.diku.dk/~mthorup/">Mikkel Thorup</a> for his invaluable contributions to this paper.Research Bloghttps://plus.google.com/101673966767287570260noreply@blogger.com0tag:blogger.com,1999:blog-21224994.post-70975319191334731112016-09-20T10:00:00.000-07:002016-09-20T10:00:16.001-07:00The 280-Year-Old Algorithm Inside Google Trips<span class="byline-author">Posted by Bogdan Arsintescu, Software Engineer & Sreenivas Gollapudi, Kostas Kollias, Tamas Sarlos and Andrew Tomkins, Research Scientists<br /></span><br /><br /><a href="https://en.wikipedia.org/wiki/Algorithm_engineering">Algorithms Engineering</a> is a lot of fun because algorithms do not go out of fashion: one never knows when an oldie-but-goodie might come in handy. Case in point: Yesterday, Google <a href="https://googleblog.blogspot.com/2016/09/see-more-plan-less-try-google-trips.html">announced Google Trips</a>, a new app to assist you in your travels by helping you create your own “perfect day” in a city. Surprisingly, deep inside Google Trips, there is an algorithm that was invented 280 years ago. <br /><br />In 1736, <a href="https://en.wikipedia.org/wiki/Leonhard_Euler">Leonhard Euler</a> authored a brief but <a href="http://eulerarchive.maa.org//docs/originals/E053.pdf">beautiful mathematical paper</a> regarding the town of Königsberg and its 7 bridges, shown here:<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-HRkkgmmGB3Y/V-Fk43DGYkI/AAAAAAAABNw/j5c6gQMUsjAWtMWwMBnQ-D35sA8l0-McQCLcB/s1600/image05.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="504" src="https://4.bp.blogspot.com/-HRkkgmmGB3Y/V-Fk43DGYkI/AAAAAAAABNw/j5c6gQMUsjAWtMWwMBnQ-D35sA8l0-McQCLcB/s640/image05.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Image from <a href="https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg">Wikipedia</a></td></tr></tbody></table>In the paper, Euler studied the following question: is it possible to walk through the city crossing each bridge exactly once? As it turns out, for the city of Königsberg, the answer is no. To reach this answer, Euler developed a general approach to represent any layout of landmasses and bridges in terms of what he dubbed the <i>Geometriam Situs</i> (the “Geometry of Place”), which we now call <a href="https://en.wikipedia.org/wiki/Graph_theory">Graph Theory</a>. He represented each landmass as a “node” in the graph, and each bridge as an “edge,” like this:<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-wRl8WjuCA-c/V-FkPmiZK-I/AAAAAAAABNs/Z9htxAzYeyg_C44uNKdjCYVLoQqaaQHuwCLcB/s1600/Screen%2BShot%2B2016-09-20%2Bat%2B9.26.46%2BAM.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="146" src="https://1.bp.blogspot.com/-wRl8WjuCA-c/V-FkPmiZK-I/AAAAAAAABNs/Z9htxAzYeyg_C44uNKdjCYVLoQqaaQHuwCLcB/s640/Screen%2BShot%2B2016-09-20%2Bat%2B9.26.46%2BAM.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Image from <a href="https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg">Wikipedia</a></td></tr></tbody></table>Euler noticed that if all the nodes in the graph have an even number of edges (such graphs are called “Eulerian” in his honor) then, and only then, a cycle can be found that visits every edge exactly once. Keep this in mind, as we’ll rely on this fact later in the post.<br /><br />Our team in Google Research has been fascinated by the “Geometry of Place” for some time, and we started investigating a question related to Euler’s: rather than visiting just the bridges, how can we visit as many interesting places as possible during a particular trip? We call this the “itineraries” problem. Euler didn’t study it, but it is a well known topic in Optimization, where it is often called the “<a href="http://chekuri.cs.illinois.edu/papers/orienteering-journal.pdf">Orienteering</a>” problem.<br /><br />While Euler’s problem has an efficient and exact solution, the itineraries problem is not just hard to solve, it is hard to even <i>approximately</i> solve! The difficulty lies in the interplay between two conflicting goals: first, we should pick great places to visit, but second, we should pick them to allow a good itinerary: not too much travel time; don’t visit places when they’re closed; don’t visit too many museums, etc. Embedded in such problems is the challenge of finding efficient routes, often referred to as the <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Travelling Salesman Problem</a> (TSP).<br /><br /><b>Algorithms for Travel Itineraries</b><br /><br />Fortunately, the real world has a property called the “<a href="https://en.wikipedia.org/wiki/Triangle_inequality">triangle inequality</a>” that says adding an extra stop to a route never makes it shorter. When the underlying geometry satisfies the triangle inequality, the TSP can be approximately solved using another <a href="https://en.wikipedia.org/wiki/Christofides_algorithm">algorithm discovered by Christofides</a> in 1976. This is an important part of our solution, and builds on Euler’s paper, so we’ll give a quick four-step rundown of how it works here:<br /><ol><li>We start with all our destinations separate, and repeatedly connect together the closest two that aren’t yet connected. This doesn’t yet give us an itinerary, but it does connect all the destinations via a <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree">minimum spanning tree</a> of the graph.</li><li>We take all the destinations that have an odd number of connections in this tree (Euler proved there must be an even number of these), and carefully pair them up.</li><li>Because all the destinations now have an even number of edges, we’ve created an Eulerian graph, so we create a route that crosses each edge exactly once.</li><li>We now have a great route, but it might visit some places more than once. No problem, we find any double visits and simply bypass them, going directly from the predecessor to the successor.</li></ol>Christofides gave an elegant proof that the resulting route is always close to the shortest possible. Here’s an example of the Christofides’ algorithm in action on a location graph with the nodes representing places and the edges with costs representing the travel time between the places.<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-DYlLoNxg-S8/V-FlOHLF8TI/AAAAAAAABN0/kNISdLQvX6cfWAmjT8k-LKPEMJA63nX-ACLcB/s1600/image04.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="172" src="https://3.bp.blogspot.com/-DYlLoNxg-S8/V-FlOHLF8TI/AAAAAAAABN0/kNISdLQvX6cfWAmjT8k-LKPEMJA63nX-ACLcB/s640/image04.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Construction of an Eulerian Tour in a location graph</td></tr></tbody></table>Armed with this efficient route-finding subroutine, we can now start building itineraries one step at a time. At each step, we estimate the benefit to the user of each possible new place to visit, and likewise estimate the cost using the Christofides algorithm. A user’s benefit can be derived from a host of natural factors such as the popularity of the place and how different the place is relative to places already visited on the tour. We then pick whichever new place has the best benefit per unit of extra cost (e.g., time needed to include the new place in the tour). Here’s an example of our algorithm actually building a route in London using the location graph shown above:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-y_t6IG5RMuE/V-Flb6RQktI/AAAAAAAABN4/91je5cQumFcOI5bgJIliDkk3tX3MoPoAgCLcB/s1600/image01.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="274" src="https://3.bp.blogspot.com/-y_t6IG5RMuE/V-Flb6RQktI/AAAAAAAABN4/91je5cQumFcOI5bgJIliDkk3tX3MoPoAgCLcB/s640/image01.png" width="640" /></a></div><b>Itineraries in Google Trips</b><br /><br />With our first good approximate solution to the itineraries problem in hand, we started working with our colleagues from the Google Trips team, and we realized we’d barely scratched the surface. For instance, even if we produce the absolute perfect itinerary, any particular user of the system will very reasonably say, “That’s great, but all my friends say I also need to visit this other place. Plus, I’m only around for the morning, and I don’t want to miss this place you listed in the afternoon. And I’ve already seen Big Ben twice.” So rather than just producing an itinerary once and calling it a perfect day, we needed a fast dynamic algorithm for itineraries that users can modify on the fly to suit their individual taste. And because many people have bad data connections while traveling, the solution had to be efficient enough to run disconnected on a phone.<br /><br /><b>Better Itineraries Through the Wisdom of Crowds</b><br /><br />While the algorithmic aspects of the problem were highly challenging, we realized that producing high-quality itineraries was just as dependent on our understanding of the many possible stopping points on the itinerary. We had Google’s extensive travel database to identify the interesting places to visit, and we also had great data from Google’s existing systems about how to travel from any place to any other. But we didn’t have a good sense for how people typically move through this geometry of places. <br /><br />For this, we turned to the wisdom of crowds. This type of wisdom is used by Google to <a href="https://googleblog.blogspot.com/2007/02/stuck-in-traffic.html">estimate delays on highways</a>, and to discover <a href="https://support.google.com/business/answer/6263531?hl=en">when restaurants are most busy</a>. Here, we use the same techniques to learn about common visit sequences that we can stitch together into itineraries that feel good to our users. We combine Google's knowledge of <a href="https://techcrunch.com/2015/07/28/google-search-now-shows-you-when-local-businesses-are-busiest/">when places are popular</a>, with the directions between those places to gather an idea of what tourists like to do when travelling.<br /><br />And the crowd has a lot more wisdom to offer in the future. For example, we noticed that visits to Buckingham Palace spike around 11:30 and stay a bit longer than at other times of the day. This seemed a little strange to us, but when we looked more closely, it turns out to be the time of the <a href="https://www.royalcollection.org.uk/visit/buckinghampalace/what-to-see-and-do/changing-the-guard">Changing of the Guard</a>. We’re looking now at ways to incorporate this type of timing information into the itinerary selection algorithms.<br /><br />So give it a try: Google Trips, available now on <a href="https://play.google.com/store/apps/details?id=com.google.android.apps.travel.onthego">Android</a> and <a href="https://itunes.apple.com/app/id1081561570?mt=8">iOS</a>, has you covered from departure to return. Research Bloghttps://plus.google.com/101673966767287570260noreply@blogger.com0tag:blogger.com,1999:blog-21224994.post-58222562181349520782016-09-15T11:00:00.000-07:002017-01-18T12:12:23.768-08:00Research from VLDB 2016: Improved Friend Suggestion using Ego-Net Analysis<span class="byline-author">Posted by Alessandro Epasto, Research Scientist, Google Research NY</span><br /><br />On September 5 - 9, New Delhi, India hosted the <a href="http://vldb2016.persistent.com/">42nd International Conference on Very Large Data Bases</a> (VLDB), a premier annual forum for academic and industry research on databases, data management, data mining and data analytics. Over the past several years, Google has actively participated in VLDB, both as official sponsor and with numerous contributions to the research and industrial tracks. In this post, we would like to share the research presented in one of the Google papers from VLDB 2016. <br /><br />In <a href="http://www.vldb.org/pvldb/vol9/p324-epasto.pdf"><i>Ego-net Community Mining Applied to Friend Suggestion</i></a>, co-authored by Googlers <a href="http://research.google.com/pubs/SilvioLattanzi.html">Silvio Lattanzi</a>, <a href="http://research.google.com/pubs/mirrokni.html">Vahab Mirrokni</a>, Ismail Oner Sebe, <a href="http://research.google.com/pubs/AhmedTaei.html">Ahmed Taei,</a> Sunita Verma and <a href="http://research.google.com/pubs/AlessandroEpasto.html">myself,</a> we explore how social networks can provide better friend suggestions to users, a challenging practical problem faced by all social network platforms<br /><br />Friend suggestion – the task of suggesting to a user the contacts she might already know in the network but that she hasn’t added yet – is major driver of user engagement and social connection in all online social networks. Designing a high quality system that can provide relevant and useful friend recommendations is very challenging, and requires state-of-the-art machine learning algorithms based on a multitude of parameters. <br /><br />An effective family of features for friend suggestion consist of <a href="https://en.wikipedia.org/wiki/Graph_(mathematics)">graph</a> features such as the <i>number of common friends </i>between two users. While widely used, the number of common friends has some major drawbacks, including the following which is shown in Figure 1.<br /><div class="separator" style="clear: both; text-align: center;"></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-88-zF6lIbX0/V9rekNAup4I/AAAAAAAABMY/EdJuYRKPC3sE6xfgOeV5xJogkaewvG3JACLcB/s1600/image01.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="492" src="https://4.bp.blogspot.com/-88-zF6lIbX0/V9rekNAup4I/AAAAAAAABMY/EdJuYRKPC3sE6xfgOeV5xJogkaewvG3JACLcB/s640/image01.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Figure 1: Ego-net of Sally.</td></tr></tbody></table>In this figure we represent the social connections of Sally and her friends – the <i>ego-net</i> of Sally. An ego-net of a node (in this case, Sally) is defined as the graph that contains the node itself, all of the node’s neighbors and the connection among <i>those</i> nodes. Sally has 6 friends in her ego-net: <b>A</b>lbert (her husband), <b>B</b>rian (her son), <b>C</b>harlotte (her mother) as well as <b>U</b>ma (her boss), <b>V</b>incent and <b>W</b>ally (two of her team members). Notice how <b>A</b>, <b>B</b> and <b>C</b> are all connected with each other while they do not know <b>U</b>, <b>V</b> or <b>W</b>. On the other hand <b>U,</b> <b>V</b> and <b>W</b> have all added each other as their friend (except <b>U</b> and <b>W</b> who are good friend but somehow forgot to add each other).<br /><br />Notice how each of <b>A</b>, <b>B</b>, <b>C</b> have a common friend with each of <b>U</b>, <b>V</b> and <b>W</b>: Sally herself. A friend recommendation system based on common neighbors might suggest to Sally’s son (for instance) to add Sally’s boss as his friend! In reality the situation is even more complicated because users’ online and offline friends span several different social circles or communities (family, work, school, sports, etc). <br /><br />In our paper we introduce a novel technique for friend suggestions based on independently analyzing the ego-net structure. The main contribution of the paper is to show that it is possible to provide friend suggestions efficiently by constructing all ego-nets of the nodes in the graph and then independently applying community detection algorithms on them in large-scale <a href="https://en.wikipedia.org/wiki/MapReduce">distributed systems</a>. <br /><br />Specifically, the algorithm proceeds by constructing the ego-nets of all nodes and applying, independently on each of them, a community detection algorithm. More precisely the algorithm operates on so-called “ego-net-minus-ego” graphs, which is defined as the graph including only the neighbors of a given node, as shown in the figure below.<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-4taXubdlCw0/V9re8hjeM3I/AAAAAAAABMg/p8HMW4Ztsy4NL973u2fT-xHz0HHyfaM1ACLcB/s1600/image00.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="530" src="https://2.bp.blogspot.com/-4taXubdlCw0/V9re8hjeM3I/AAAAAAAABMg/p8HMW4Ztsy4NL973u2fT-xHz0HHyfaM1ACLcB/s640/image00.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Figure 2: Clustering of the ego-net of Sally.</td></tr></tbody></table>Notice how in this example the ego-net-minus-ego of Sally has two very clear communities: her family (<b>A</b>, <b>B</b>, <b>C</b>) and her co-workers (<b>U</b>, <b>V</b>, <b>W</b>) which are easily separated. Intuitively, this is because one might expect that while nodes (e.g. Sally) participate in many communities, there is usually a single (or a limited number of) contexts in which two specific neighbors interact. While Sally is both part of her family and work community, Sally and Uma interact <i>only</i> at work. Through extensive experimental evaluation on large-scale public social networks and formally through a simple mathematical model, our paper confirms this intuition. It seems that while communities are hard to separate in a global graph, they are easier to identify at the local level of ego-nets. <br /><br />This allows for a novel graph-based method for friend suggestion which intuitively only allows suggestion of pairs of users that are clustered together in the same community from the point of view of their common friends. With this method, <b>U</b> and <b>W</b> will be suggested to add each other (as they are in the same community and they are not yet connected) while <b>B</b> and <b>U</b> will <i>not</i> be suggested as friends as they span two different communities. <br /><br />From an algorithmic point of view, the paper introduces efficient parallel and distributed techniques for computing and clustering all ego-nets of very large graphs at the same time – a fundamental aspect enabling use of the system on the entire world Google+ graph. We have applied this feature in the “You May Know” system of Google+, resulting in a clear positive impact on the prediction task, improving the acceptance rate by more than 1.5% and decreasing the rejection rate by more than 3.3% (a significative impact at Google scales).<br /><br />We believe that many future directions of work might stem from our preliminary results. For instance ego-net analysis could be potentially to automatically classify a user contacts in circles and to detect spam. Another interesting direction is the study of ego-network evolution in dynamic graphs. Research Bloghttps://plus.google.com/101673966767287570260noreply@blogger.com0