The word social is currently in vogue, we have social networking, social software, social bookmarking, and now social algorithm. Social networking is the activity, social software are the tools which make social networking possible, but what is a social algorithm?
The following tries to define what a social algorithm is.
Let us look at the examples. Famous social networking sites include Flickr, YouTube, MySpace, Friendster, Wikipedia, Facebook, del.icio.us and the the virtual gaming world of Second Life. Bookmarking and tagging are considered social network activities. The purpose of the network is for people to rendezvous, collaborate, or just sharing something (photos, music, movies, information, etc).
Social software are the tools which make it possible for people to network. These range from email, mailing lists, RSS, IRC, instant messaging, Napster like P2P, blogs, wikis, AJAX, Web 2, etc. Their characteristic is that the networking must be interactive, and bottom-up (users provide content). These software used to be called group-ware. Some of these software are quite old, but some others like blogs are more recent. Wikis have been around ever since Ward Cunningham, the father of Wiki started it, but it was then considered for geeks only, and have been accepted widely only in the last couple of years. Some software are documented using wikis, and businesses, educational institutions have started to make use of it.
So, what is a social algorithm? An algorithm is like a cooking recipe or computer program with step-by-step instructions to execute a procedure. Algorithms are stated in pseudo-code, easy for people to understand, and are more abstract than computer programs. The programs are said to implement some algorithm, being a machine level translation of the pseudo-code.
Although most algorithms are numerical, they need not be, as shown in cooking recipes, logical unification algorithm, string matching, face recognition, etc.
Social algorithms differs from general algorithms in that they involve agents, and the algorithm is the result of the interaction of the agents. The ant colony algorithm is an example, with ants as the agents, and used to solve some problem, such as the shortest path or the traveling salesman problem. Social algorithms can used for distributed problem solving as the ant colony algorithm, but need not be.
It is said that Google’s PageRank algorithm is the decisive factor for Google to win the battle of the web. The PageRank algorithm ranks websites using many criteria, including the number of inbound links, each with a weight which is the PageRank of the referring site (the algorithm is recursive and almost real-time).
To have an idea of the algorithm, here is a description:
The original PageRank algorithm was described by Lawrence Page and Sergey Brin in several publications.
It is given by
PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
PR(A) is the PageRank of page A,
PR(Ti) is the PageRank of pages Ti which link to page A,
C(Ti) is the number of outbound links on page Ti and
d is a damping factor which can be set between 0 and 1.
Since PageRank defines ranking of sites in a search, it affects many things, and in the last analysis, many people who derive income from the sites. Hence people, who are the agents here, try to modify their site parameters to increase their ranks. This is commonly known as SEO: search engine optimization.
This is an example where the algorithm provides rules for the social network, and in so doing modifies the agents behavior or actions. Abuse of the algorithm have occurred, in one case, someone builds websites based on (almost) links only with no content, but manages to get a high PageRank. Such anomalies will be probably be taken care of, as the PageRank algorithm is also evolving.
Internet auctions and reverse auctions such as provided by EBay, are also algorithms which provide the rules of the game, where we are the players.
Digg.com is a social bookmarking site, the original suggestion is given 1 digg, and people can digg again if they like the suggestion, or undug it if they don’t. The number of diggs in indicative of the suggestion’s popularity. This system will favor groups of people who collaborate to digg each other suggestions.
We see that social algorithms have weaknesses, often exploited by certain people. Hence the need for improving social algorithms.
Netflix is a famous case, they have offered one million dollars to anyone who can improve the accuracy of their existing algorithm by 10%.
Non human players and avatars.
Back to the definition of social algorithm as a multi-agent based algorithm, where the agents are people, we feel that this definition must be enlarged to include cases where people are substituted by animals or software surrogates. I would consider a simulation of the Digg algorithm, or a simulation of market trading using intelligent agents as social algorithms. So is the ant colony algorithm, which substitutes animals for people. Likewise swarms, flocks, etc.
Cellular automata is a border case, it is agent based all right, but often used to simulate physical, and chemical processes. If use to mimic human activity, it would be a social algorithm.
The evolution algorithm as an abstraction of the Darwinian process is also a social algorithm.
Genetic algorithms and its variations are included here.
Evolutionary Game Theory.
The field of social algorithms intersects with evolutionary game theory. Game theory studies strategies use by the agents, for example in trading, auctions, marketing, voting etc. The prisoner’s dilemma sets a game for 2 prisoners, but it can be iterated and played in a population, which then becomes a social algorithm.
If you have ever played Second Life, you know how complicated social algorithms can be. In the virtual world, the whole life, including economics, relations, and property, is defined by algorithms.