algorithm to find relationship of two twitter users -


i have 6 degrees of kevin bacon type problem. lets have 2 twitter users , want figure out relationship each other through friends (i use friends denote when follow vs them following you) , followers in twitter. have id's in database.

so example:

joel , sally

joel follows fred friends steve follows sally.

there multiple ways there, want shortest.

this seems known computer science problem (shortest path algorihm).

today have table called "influencers" twitter ids stored, have followings table self referential table (ids of followers on 1 side , friends on other.)

so graph theory? if can point me utilities/libraries/approaches can helpful. im using ruby, can parse languages.

as have said, known problem, can see in wikipedia.

just notice in case, weights in edges equal 1), don't think djikstra's algorithm useful you.

in order find minimum distance, suggest breadth-first search. problem twitter network may extremelly connected , hence may have combinatorial explosion (imagine each person connected 20 other persons - in first level, visit 20 profiles, while in next visit 400, , in next 8000 - if don't find sally fast, run out of memory).

there linear programming formulation, not 100% familiar. these notes on linear programming, not on shortest path problem, while these seem more focused on applications.

there video lecture on problem available on line seem quite complete.

i hope these references help.


Comments

Post a Comment

Popular posts from this blog

java - Play! framework 2.0: How to display multiple image? -

i need display gallery of photos. here template: @(photos: list[photo]) @title = { <bold>gallery</bold> } @main(title,"photo"){ <ul class="thumbnails"> @for(photo <- photos) { <li class="span3"> <a href="#" class="thumbnail"> <img src="@photo.path" alt=""> </a> </li> } </ul> } and here controller method: public static result getphotos() { return ok(views.html.photo.gallery.render(photo.get())); } and here photo bean : @entity public class photo extends model { @id public long id; @required public string label; public string path; public photo(string path, string label) { this.path = path; this.label = label; } private static finder<long, photo> find = new finder<long, photo>( long.class, photo.class); public static list<phot...
Read more

gmail - Is there any documentation for read-only access to the Google Contacts API? -

i want read-only access user's google contacts. there stackoverflow member wanted this, , received following answer : yes, there is, use https://www.googleapis.com/auth/contacts.readonly scope , "view contacts". this exchange reference read-only access google contacts can find using google. simply using access token obtained attempt read usual google contacts api (i.e. https://www.google.com/m8/feeds ) fails insufficient permissions. similarly, using google contacts api on new target fails 404 errors (for example https://www.googleapis.com/auth/contacts.readonly/default/full ). is there documentation anywhere on how use api, or permissible way access google contacts api full read-write access?
Read more

php - Controller/JToolBar not working in Joomla 2.5 -

relevant code: jtoolbarhelper::custom('savecategories', 'save', '', 'save', false, false); ... <input type="hidden" name="controller" value="easyblogcontroller"> according can dig docs , own previous questions, should call savecategories() function in easyblogcontroller . i've tried setting value easyblog , easyblog.php (file name) current easyblogcontroller (class name). clicking on save button refreshes page. not redirect, echo or var_dump test code put in savecategories() function. var_dump ing jrequest::getvar('controller') , 'task' return correct values. creating controller object , using $controller->execute('task'); works. the values going depend on location of controller trying call, , have couple options here. typically there controller in base folder of component (likely components/com_easyblog) in file called controller.php , class name inside ...
Read more