2014/01/14 by Alexander V. Mantzaris, Mantzaris, Alexander V.
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Opinion Dynamics and Social Influence #Peer-to-Peer Network Technologies #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1401.3222
openalex publication_date 2014/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
From many datasets gathered in online social networks, well defined community\nstructures have been observed. A large number of users participate in these\nnetworks and the size of the resulting graphs poses computational challenges.\nThere is a particular demand in identifying the nodes responsible for\ninformation flow between communities; for example, in temporal Twitter networks\nedges between communities play a key role in propagating spikes of activity\nwhen the connectivity between communities is sparse and few edges exist between\ndifferent clusters of nodes. The new algorithm proposed here is aimed at\nrevealing these key connections by measuring a node's vicinity to nodes of\nanother community. We look at the nodes which have edges in more than one\ncommunity and the locality of nodes around them which influence the information\nreceived and broadcasted to them. The method relies on independent random walks\nof a chosen fixed number of steps, originating from nodes with edges in more\nthan one community. For the large networks that we have in mind, existing\nmeasures such as betweenness centrality are difficult to compute, even with\nrecent methods that approximate the large number of operations required. We\ntherefore design an algorithm that scales up to the demand of current big data\nrequirements and has the ability to harness parallel processing capabilities.\nThe new algorithm is illustrated on synthetic data, where results can be judged\ncarefully, and also on a real, large scale Twitter activity data, where new\ninsights can be gained.\n