Research On Node Influence Estimation In Large Scale Bipartite Graph

Node influence estimation is an emerging research topic in network graph analysis.Researchers find that centrality metrics,which describe the connectivity and topology of a graph,do not perform well in estimating node influence.For example,a node with high degree centrality does not necessarily have the power to quickly spread a rumor to a large number of nodes in the network graph.As a comparison,simulations on epidemics,such as virus spreading models,are more accurate in evaluating node influence in a graph.However,when graph is large,neither complex centrality metrics nor epidemic simulations is computationally feasible.It is an open problem to accurately and efficiently find highly influential nodes in large scale graphs.In this dissertation,we propose to estimate a node’s influence only using information from its close proximity,namely neighborhood spectrum,and we define two new node influence metric,namely neighborhood spectrum fan-out coefficient and propagation power.The metrics derived from a node’s neighborhood spectrum can better represent its influence than traditional centrality metrics.Moreover,based on bucket sorting,we propose highly efficient algorithms that can calculate neighborhood spectrum in bipartite graphs with billions or more edges.We conduct experiments in graphs of different scale and topology.The results prove that our proposed algorithms and metrics are effective in estimating node influences for both small scale graphs and large scale bipartite graphs.