Remarks on Category-Based Routing in Social Networks

Details Remarks on Category-Based Routing in Social Networks Remarks on Category-Based Routing in Social Networks

2012-02-10

arxiv.org/abs/1202.2293v2

Computer Science

Social and Information Networks

Scientific paper

It is well known that individuals can route messages on short paths through social networks, given only simple information about the target and using only local knowledge about the topology. Sociologists conjecture that the routes are found greedily by passing the message to an acquaintance that has more in common with the target than the current holder of the message, e.g. if a dentist in Saarbr\"ucken wants to send a message to a specific lawyer in Munich, he may forward it to someone who is a lawyer and/or lives in Munich. Modelling this setting, Eppstein et al. introduced the notion of category-based routing. The goal is to assign a set of categories to each node of a graph such that the categories are connected, greedy routing is possible, and the maximal number of categories a node is in is minimal. We give an improved upper bound construction and show lower bounds for stars, trees, and general graphs.

Affiliated with

Also associated with

No associations

Rating

Remarks on Category-Based Routing in Social Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Remarks on Category-Based Routing in Social Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Remarks on Category-Based Routing in Social Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-276042