views:

339

answers:

2

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

+1  A: 

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.

Mike Howard
@Mike: Thanks for replying. I have read the paper. I wish to know more algorithms other than those given in the paper.
Bruce
A Link to "Searching for expertise in social networks" : http://www.eecs.umich.edu/~ackerm/pub/05b38/zhang-ackerman.group05.final.pdf
Hannson
i wasnt put vote for ur answer
ratty
A: 

[PDF] Complex networks and decentralized search algorithms

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

ratty
I see my answer has been voted down to zero about the same time this answer was given... any particular issue with it or just all fair in love and war? :-)
Mike Howard