Header menu link for other important links
X
Centrality measures, upper bound, and influence maximization in large scale directed social networks
S.K. Pal, , C.A. Murthy
Published in
2014
Volume: 130
   
Issue: 3
Pages: 317 - 342
Abstract
The paper addresses the problem of finding top k influential nodes in large scale directed social networks. We propose two new centrality measures, Diffusion Degree for independent cascade model of information diffusion and Maximum Influence Degree. Unlike other existing centrality measures, diffusion degree considers neighbors' contributions in addition to the degree of a node. The measure also works flawlessly with non uniform propagation probability distributions. On the other hand, Maximum Influence Degree provides the maximum theoretically possible influence (Upper Bound) for a node. Extensive experiments are performed with five different real life large scale directed social networks. With independent cascade model, we perform experiments for both uniform and non uniform propagation probabilities. We use Diffusion Degree Heuristic (DiDH) and Maximum Influence Degree Heuristic (MIDH), to find the top k influential individuals. k seeds obtained through these for both the setups show superior influence compared to the seeds obtained by high degree heuristics, degree discount heuristics, different variants of set covering greedy algorithms and Prefix excluding Maximum Influence Arborescence (PMIA) algorithm. The superiority of the proposed method is also found to be statistically significant as per T-test.
CONTINUE READING
Figures & Tables (16)
  • Figure-0
    Figure 1. A sample network. Nodes are sized as per their ... Expand
  • Figure-1
    Figure 2. Block diagram & flow chart
  • Figure-2
    Table 1. Features of Data Sets
  • Figure-3
    Figure 3. Plot of α with k for Twitter network on UPP setup
  • Figure-4
    Figure 4. Assigned Propagation Probability Distribution (PPD) ... Expand
  • Figure-5
    Figure 5. Assigned PPD and corresponding results for Twitter
  • Figure-6
    Figure 6. Assigned PPD and corresponding results for Twitter
  • Figure-7
    Figure 7. Plot of α for seven nodes with distance on Twitter ... Expand
  • 8 figures hidden
    Show all figures
About the journal
JournalFundamenta Informaticae
ISSN01692968