This is the continuation of the previous post- Its is a Small World.. Is it ?. From the Millgram's "Small World" experiment,the average length of the resulting chains for the letters that eventually reached the target was about six. So, if the study is correct, how can we find out such a path, among the many different possible paths in the network, So the real challenge is that even though two people are connected by a short path , how can they be able to find it. Remember that the experiment dint use a broadcast search rather a directed search.i.e., Subjects didn't pass on the letter to all the possible people they know, only the one person that they thought would know the target.
Although broadcast search would in principle would give the shortest path to the target, it would be practically impossible. So even in theory if we are only six degrees away from anybody else in the world, there are still 7 billion people in this world and at least as many path leading to them,how can we find the short path that we are looking for?
We can start taking best guesses at every step, if first guess is wrong or if the subsequent guesses are wrong we will end up in a blind alley. Even if we are proceeding in the right direction there is no way to know how well we are progressing .At each degree of separation we have a new decision to make and no clear way to evaluate our options. The problem with this approach is that "We are trying to solve a global problem using only the local information of the network". Though six sounds like a small number ,it is very big number when it comes to directed searches in fact anything over two is big.
Instead of focusing on just the existence of short paths , we can approach the problem by thinking how people in the network actually find those paths.People in fact have a strong notion of distance that they use all time to differentiate themselves from others. What makes the search problem feasible is that no one person has to solve it on his own.Rather at each step, all a particular sender has to worry about is getting the message in to the next phase of search,where a phase is like a different region. In doing so, we are assuming that the next person in the chain,being closer to the target has more precise information than you do ,and so is better able to advance the search in to the next phase.
In order for social connections to be useful,they have to encode information about the underlying social structure[like the regions of a map]. The distance in social networks is that we can "measure" it in two different ways, social distance[in terms of how we tend to identify ourselves and others in terms of groups,institutions and activities with which we are affiliated with], which can be measured globally but which is not a true distance (and hence can yield misleading estimates); and network paths, which generate true distances but which are known only locally.
Individuals simply don't belong to groups.They also have a way of arranging them in a kind of social space so as to measure their similarity or differences with others.How they do this is , by starting out at the the level of whole world, individuals break it down, in to a manageable number of smaller more specific categories,subcategories so on. this continues to be like the below image.
The distance between A and B is the height of the lowest common-ancestor group, which in this case is three.Individuals in the same level are distance one apart.The higher up the hierarchy one has to got to find a common grouping the more distant the individuals will be.There are many kinds of distances which we might refer when accessing the likelihood that two people will meet, Individuals in real world would derive their notions of distance from an assortment of social dimensions[geographical proximity, working in same org, studies in same college, like similar music etc.,].
Individuals A,B,C in two dimensions. A and C are close geographically , and B and C are close in occupation. Hence, C perceives itself to be close to both A ans B but A and B perceive each other as distance. If two people are close in only one dimension consider them close even if they are quite distant in other dimensions.
Social distance emphasizes similarities over differences. As long as individuals more likely to know other people like them ,and as long as they measure similarity along more than one social dimension,then not only will short paths exist between anyone almost anywhere , but also individuals with only local information about network will be able to find them.
Also a surprising fact is that the best performance was achieved when the number of dimensions was only about two or three.When everyone is using only one dimension to parse the worlds they cant take advantage of multiple affiliations to hop large distances in social space. And where everyone spread out their contacts among too many dimensions -- when none of your friends belong to the same networks-- then we are back to the world of random networks where short paths exists but can't be found. Hence Searchable networks lie somewhere in the middle where individuals are neither too uni dimensional or too scattered.
Efficient decentralized searches can e conducted by means of simple, greedy algorithms providing only that the characteristics of the target element and the current element's immediate neighbors are known.A simple algorithm that combines knowledge of network ties and social identity can succeed in directing messages efficiently. The algorithm[Ref 1] is the same greedy algorithm Millgram suggested: Each member i of a message chain forwards the message to its neighbor j who is closest to the target t in terms of social distance; that is,yjt is minimized over all j ini's network neighborhood.
The same approach of search is employed in many other disciplines like Peer-to-Peer Networks Search , distributed databases etc.,
References:
1. http://www.sciencemag.org/content/296/5571/1302.full
2. http://www.amazon.com/Duncan-J.-Watts/e/B001ILHHR4/ref=ntt_athr_dp_pel_1
Although broadcast search would in principle would give the shortest path to the target, it would be practically impossible. So even in theory if we are only six degrees away from anybody else in the world, there are still 7 billion people in this world and at least as many path leading to them,how can we find the short path that we are looking for?We can start taking best guesses at every step, if first guess is wrong or if the subsequent guesses are wrong we will end up in a blind alley. Even if we are proceeding in the right direction there is no way to know how well we are progressing .At each degree of separation we have a new decision to make and no clear way to evaluate our options. The problem with this approach is that "We are trying to solve a global problem using only the local information of the network". Though six sounds like a small number ,it is very big number when it comes to directed searches in fact anything over two is big.
Instead of focusing on just the existence of short paths , we can approach the problem by thinking how people in the network actually find those paths.People in fact have a strong notion of distance that they use all time to differentiate themselves from others. What makes the search problem feasible is that no one person has to solve it on his own.Rather at each step, all a particular sender has to worry about is getting the message in to the next phase of search,where a phase is like a different region. In doing so, we are assuming that the next person in the chain,being closer to the target has more precise information than you do ,and so is better able to advance the search in to the next phase.
In order for social connections to be useful,they have to encode information about the underlying social structure[like the regions of a map]. The distance in social networks is that we can "measure" it in two different ways, social distance[in terms of how we tend to identify ourselves and others in terms of groups,institutions and activities with which we are affiliated with], which can be measured globally but which is not a true distance (and hence can yield misleading estimates); and network paths, which generate true distances but which are known only locally.
Individuals simply don't belong to groups.They also have a way of arranging them in a kind of social space so as to measure their similarity or differences with others.How they do this is , by starting out at the the level of whole world, individuals break it down, in to a manageable number of smaller more specific categories,subcategories so on. this continues to be like the below image.
The distance between A and B is the height of the lowest common-ancestor group, which in this case is three.Individuals in the same level are distance one apart.The higher up the hierarchy one has to got to find a common grouping the more distant the individuals will be.There are many kinds of distances which we might refer when accessing the likelihood that two people will meet, Individuals in real world would derive their notions of distance from an assortment of social dimensions[geographical proximity, working in same org, studies in same college, like similar music etc.,].
Social distance emphasizes similarities over differences. As long as individuals more likely to know other people like them ,and as long as they measure similarity along more than one social dimension,then not only will short paths exist between anyone almost anywhere , but also individuals with only local information about network will be able to find them.
Also a surprising fact is that the best performance was achieved when the number of dimensions was only about two or three.When everyone is using only one dimension to parse the worlds they cant take advantage of multiple affiliations to hop large distances in social space. And where everyone spread out their contacts among too many dimensions -- when none of your friends belong to the same networks-- then we are back to the world of random networks where short paths exists but can't be found. Hence Searchable networks lie somewhere in the middle where individuals are neither too uni dimensional or too scattered.
Efficient decentralized searches can e conducted by means of simple, greedy algorithms providing only that the characteristics of the target element and the current element's immediate neighbors are known.A simple algorithm that combines knowledge of network ties and social identity can succeed in directing messages efficiently. The algorithm[Ref 1] is the same greedy algorithm Millgram suggested: Each member i of a message chain forwards the message to its neighbor j who is closest to the target t in terms of social distance; that is,yjt is minimized over all j ini's network neighborhood.
The same approach of search is employed in many other disciplines like Peer-to-Peer Networks Search , distributed databases etc.,
References:
1. http://www.sciencemag.org/content/296/5571/1302.full
2. http://www.amazon.com/Duncan-J.-Watts/e/B001ILHHR4/ref=ntt_athr_dp_pel_1
No comments:
Post a Comment