Algorithm for performing decentralized search in social networks

I want to find out all the existing decentralized algorithms that exploit the structural properties of social networks. So far I know the following algorithms -

1) Best connected search - Adamic et al

2) Random Walk (does not exploit any structural property but still it is decentralized)

3) Hamming distance search

4) Weak/Strong tie search

5) Cosine Similarity Search (CCS)

6) Information开发者_开发知识库 Scent Search (ISS)

Any help would be appreciated

---

From the paper "Searching For Expertise in Social Networks: A Simulation of Potential Strategies":

Breadth First Search (BFS) broadcasts a query to all of one’s neighbors instead of picking a neighbor according to a heuristic. It can find the target closest to the source but with extremely high bandwidth costs (as in p2p file sharing networks).

Cosine Similarity Search (CCS) decreases the high degree impact by dividing the Hamming distance by the total number of out-degree relations (friends) a neighbor has.

Information Scent Search (ISS) picks the next person who has the highest match score (which we call information scent) between the query and his profile. Our implementation of the algorithm is slightly different from Yu and Singh, since we needed to adapt their algorithm to the Enron data set. We use the automatic generated keywords profile instead.

---

[PDF] Complex networks and decentralized search algorithms

http://www.cs.cornell.edu/home/kleinber/icm06-swn.pdf