если граф чисто - набор людей и ребра = френды, то это как раз то, что делал я. А самых влиятельных можно найти с помощью центральностей (сloseness, betweenness, PageRank, Eigen)
еще такая идея была - спарсить сообщества, в которых состоят люди и назначить вес каждому ребру между парой пересечение множеств их сообществ в каком-нибудь отнормированном виде