I just start an independent study about small world network and clusters and I try to find papers about decentralized search and clusters.

Can anyone give me some references? Thanks!

EDIT (David White): This question is from my student, and I encouraged her to ask it here. We are just starting research on decentralized search in social networks, and she had the idea to form a graph where the nodes are sets of individuals and you put an edge between two sets if there is any overlap. We'd like to write down some decentralized search algorithms (e.g. greedy, random) and analyze them. I think this is a great starting project, but I don't know enough about the literature. Has someone else already done this? Is there a name for graphs of the form above? Has anyone studied a version where you weight each edge by the size of the intersection of the two sets?

Joonas is correct that googling "decentralized search and cluster" yields many articles. I can't seem to find any which do what we're thinking of doing, but that doesn't mean they don't exist. I'd hate to steer my student in a bad direction in her first research project. Any help you can provide would be much appreciated.

  • 6
    $\begingroup$ Googling "decentralized search and clusters" gives several articles. If these do not answer your needs, can you be more specific about what you want? $\endgroup$ – Joonas Ilmavirta Jan 28 '15 at 5:52
  • 5
    $\begingroup$ See also: meta.mathoverflow.net/questions/2105/encouraging-student-users I'm going to reopen, but of course it can be reclosed if the community feels it should be. The original closing votes were justly applied; the question needed more context/specificity. $\endgroup$ – Todd Trimble Jan 28 '15 at 13:10

Those graphs are called intersection graphs. Perhaps you can find literature relevant to your problem using that name. For instance I found the following paper where they do something similar to what you want, if I understood correctly:

M. Bloznelis, Degree and clustering coefficient in sparse random intersection graphs, The Annals of Applied Probability, Vol.23, No.3, 2013.

| cite | improve this answer | |
  • $\begingroup$ Great, thanks! We will read that paper this week and see if it does what we were thinking. In the meanwhile, I hope others who know of good references won't hesitate to post. $\endgroup$ – David White Jan 31 '15 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.