Who's the most influential in a social graph? New software recognizes key influencers faster than ever

September 7, 2012 by Jason Maderer

(Phys.org)—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 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 and Engineering Ph.D. candidate Oded Green at the 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."

In some cases, betweenness centrality can be computed more than 100 times faster using the Georgia Tech software. The will soon be available to businesses.

Bader, the Institute's executive director for , says the technology has wide-ranging applications. For instance, advertisers could use the software to identify which celebrities are most influential on Twitter or Facebook, or both, during product launches.

"Despite a fragmented social media landscape, data analysts would be able to use the algorithm to look at each social media network and mark inferences about a single influencer across these different platforms," said Bader.

As another example, the algorithm could be used for traffic patterns during a wreck or traffic jam. Transportation officials could quickly determine the best new routes based on gradual side-street congestion.

Explore further: Petascale computing tools could provide deeper insight into genomic evolution

Related Stories

MIT researchers create new Urban Network Analysis toolbox

September 6, 2011

MIT researchers have created a new Urban Network Analysis (UNA) toolbox that enables urban designers and planners to describe the spatial patterns of cities using mathematical network analysis methods. Such tools can support ...

How quickly things spread

February 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information could help ...

Graph500 adds new measurement of supercomputing performance

June 26, 2012

(Phys.org) -- Supercomputing performance is getting a new measurement with the Graph500 executive committee’s announcement of specifications for a more representative way to rate the large-scale data analytics at the ...

Recommended for you

Sydney makes its mark with electronic paper traffic signs

July 28, 2015

Visionect, which is in the business of helping companies build electronic paper display products, announced that Sydney has launched e-paper traffic signs. The traffic signage integrates displays from US manufacturer E Ink ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.