At an airport, many people are essential for planes to take off. Gate staffs, refueling crews, flight attendants and pilots are in constant communication with each other as they perform required tasks. But it’s the air traffic controller who talks with every plane, coordinating departures and runways. Communication must run through her in order for an airport to run smoothly and safely.
In computational terms, the air traffic controller is the “betweenness centrality,” the most connected person in the system. In this example, finding the key influencer is easy because each departure process is nearly the same.
Determining the most influential person on a social media network (or, in computer terms, a graph) is more complex. Thousands of users are interacting about a single subject at the same time. New people (known computationally as edges) are constantly joining the streaming conversation.
Georgia Tech has developed a new algorithm that quickly determines betweenness centrality for streaming graphs. The algorithm can identify influencers as information changes within a network. The first-of-its-kind streaming tool was presented this week by Computational Science and Engineering Ph.D. candidate Oded Green at the Social Computing Conference in Amsterdam.
“Unlike existing algorithms, our system doesn’t restart the computational process from scratch each time a new edge is inserted into a graph,” said College of Computing Professor David Bader, the project’s leader. “Rather than starting over, our algorithm stores the graph’s prior centrality data and only does the bare minimal computations affected by the inserted edges.”
No pointers to the paper, yet, but the software is said to be open source.
Will make a new post when the article appears. To make sure it gets on your radar.
On obvious use of “influence” in a topic map is what topics have the most impact on the subject identities represented by other topics.
Such as if I remove person R, do we still think persons W – Z are members of a terrorist group?
Bonus question: I wonder what influence Jack Menzel, Product Management Director at Google, has in social graphs now?
PS: Just in case you want to watch for this paper to appear:
O. Green, R. McColl, and D.A. Bader, “A Fast Algorithm for Incremental Betweenness Centrality,” ASE/IEEE International Conference on Social Computing (SocialCom), Amsterdam, The Netherlands, September 3-5, 2012.
(From Prof. David A. Bader’s CV page.)