9th IEEE International Conference on Collaborative Computing: Networking, Applications and Worksharing

Research Article

Influence Maximization for Big Data Through Entropy Ranking and Min-Cut

Download693 downloads
  • @INPROCEEDINGS{10.4108/icst.collaboratecom.2013.254119,
        author={Agustin Sancen-Plaza and Andres Mendez-Vazquez},
        title={Influence Maximization for Big Data Through Entropy Ranking and Min-Cut},
        proceedings={9th IEEE International Conference on Collaborative Computing: Networking, Applications and Worksharing},
        publisher={ICST},
        proceedings_a={COLLABORATECOM},
        year={2013},
        month={11},
        keywords={influence maximization min cut entropy},
        doi={10.4108/icst.collaboratecom.2013.254119}
    }
    
  • Agustin Sancen-Plaza
    Andres Mendez-Vazquez
    Year: 2013
    Influence Maximization for Big Data Through Entropy Ranking and Min-Cut
    COLLABORATECOM
    IEEE
    DOI: 10.4108/icst.collaboratecom.2013.254119
Agustin Sancen-Plaza1, Andres Mendez-Vazquez1,*
  • 1: Cinvestav GDL
*Contact email: amendez@gdl.cinvestav.mx

Abstract

As Big Data becomes prevalent, the traditional models from Data Mining or Data Analysis, although very efficient, lack the speed necessary to process problems with data sets in the range of million samples. Therefore, the need for designing more efficient and faster algorithms for these new types of problems. Specifically, from the field of social network analysis, we have the influence maximization problem. This is a problem with many possible applications in advertising, marketing, social studies, etc, where we have representations of influences by large scale graphs. Even though, the optimal solution of this problem, the minimum set of graph nodes which can influence a maximum set of nodes, is a NP-Hard problem, it is possible to devise an approximated solution to the problem. In this paper, we have proposed a novel algorithm for influence maximization analysis. This algorithm consist in two phases: the first one is an entropy based node ranking where entropy ranking is used to determine node importance in a directed weighted influence graph. The second phase computes the minimum cut using a novel metric. To test the propose algorithm, experiments were performed in several popular data sets to evaluate performance and the seed quality over the influences.