STRIP: stream learning of influence probabilities

Konstantin Kutzkov

    Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


    Influence-driven diffusion of information is a fundamental
    process in social networks. Learning the latent variables of
    such process, i.e., the influence strength along each link, is a
    central question towards understanding the structure and
    function of complex networks, modeling information cascades,
    and developing applications such as viral marketing.

    Motivated by modern microblogging platforms, such as
    twitter, in this paper we study the problem of learning
    influence probabilities in a data-stream scenario, in which
    the network topology is relatively stable and the challenge
    of a learning algorithm is to keep up with a continuous
    stream of tweets using a small amount of time and memory.
    Our contribution is a number of randomized approximation
    algorithms, categorized according to the available
    space (superlinear, linear, and sublinear in the number of
    nodes n) and according to dierent models (landmark and
    sliding window). Among several results, we show that we
    can learn influence probabilities with one pass over the data,
    using O(n log n) space, in both the landmark model and the
    sliding-window model, and we further show that our algorithm
    is within a logarithmic factor of optimal.
    For truly large graphs, when one needs to operate with
    sublinear space, we show that we can still learn influence
    probabilities in one pass, assuming that we restrict our attention
    to the most active users.

    Our thorough experimental evaluation on large social
    graph demonstrates that the empirical performance of our
    algorithms agrees with that predicted by the theory.
    Original languageEnglish
    Title of host publicationKDD '13 Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining
    Number of pages9
    PublisherAssociation for Computing Machinery
    Publication date2013
    Pages 275-283
    ISBN (Print)978-1-4503-2174-7
    Publication statusPublished - 2013


    • streaming, influence probabilities, social networks


    Dive into the research topics of 'STRIP: stream learning of influence probabilities'. Together they form a unique fingerprint.

    Cite this