Information Flows in Online Social Networks

The project focuses on access to information via systems such as Twitter and FaceBook. Our goal is to improve the efficiency of information access via OSN’s in terms of precision/recall. To that end, we will develop solutions for recommending both content items and potential contacts to users.

Such recommender systems will be constructed from the following primitives:

  • Reward mechanisms allowing users to give feedback on specific content items;
  • Inference mechanisms that exploit the former reward mechanisms for characterizing i) types of specific content and ii) tastes and expertise of individual users.

The resulting recommender systems should be light-weight, accurate, and resilient to users’ strategic behaviors.

The expected outcomes of the project are

  1. A deeper understanding of the limits of collective processing and filtering of information in terms of precision / recall trade-offs.
  2. Optimized schemes for identification of implicit communities of like-minded users and contact recommendation for helping users “rewire” the information network for better performance.  In particular robust versions of spectral embedding and message-passing algorithms à la Belief Propagation will be elaborated in this respect. Limitations / relative merits of candidate schemes, their robustness to noise in the input data, will be investigated. Distributed mechanisms for evaluating users’ expertise on particular topics. Such “expertise” evaluation can be multi-dimensional.
  3. Active learning strategies for quick categorization of content types. In particular we will design rules for adaptively selecting users from whom to obtain feedback on content, aiming to achieve accurate content categorization based on the smallest possible number of user solicitations.
  4. Protection against selfishness of participating users: proposed reward mechanisms should induce desirable content editing and filtering by the users when they are selfishly trying to maximize their overall rewards. . We will also aim to protect the system against the attack whereby groups of users conspire and distribute among themselves rewards similar to FaceBook’s “likes” thus artificially boosting their individual expertise. A particular scheme that we will consider is an instance of the so-called “marginal utility” reward mechanism whereby a user is rewarded by the utility to others that would have been lost if this particular user had not actively participated to the system.
  5. Validation on available datasets and experimental deployment of some of the proposed mechanisms.

    Former members:
    • George Giakkoupis Inria Rennes Atlantique
    • Lennart Gulikers Microsoft Research-Inria Joint Centre (PHD Student)
    • Ian Kash Microsoft Research Cambridge
    • Anne-Marie Kermarrec Inria Rennes Atlantique
    • Peter Key Microsoft Research Cambridge
    • Arnaud Legout Inria Sophia Antipolis Méditerranée
    • Marc Lelarge Inria Paris Rocquencourt
    • Mesrob Ohanessian Microsoft Research-Inria Joint Centre (Post Doctoral Student)
    • Rémi Varloot Microsoft Research-Inria Joint Centre (PHD Student)
    • Laurent Viennot Inria Paris - Rocquencourt
    • Kuang Xu Microsoft Research-Inria Joint Centre (Post Doctoral Student)

    2019

    Pré-publication, Document de travail

    titre
    An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
    auteur
    Hadrien Hendrikx, Francis Bach, Laurent Massoulié
    article
    2019
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-02280763/file/1905.11394.pdf BibTex

    2018

    Article dans une revue

    titre
    On the Capacity of Information Processing Systems
    auteur
    Laurent Massoulié, Kuang Xu
    article
    Operations Research, INFORMS, 2018, 66 (2), pp.568-586
    Accès au bibtex
    BibTex
    titre
    An impossibility result for reconstruction in the degree-corrected stochastic block model
    auteur
    Lennart Gulikers, Marc Lelarge, Laurent Massoulié
    article
    Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2018, 28 (5), pp.3002-3027
    Accès au bibtex
    https://arxiv.org/pdf/1511.00546 BibTex
    titre
    Group synchronization on grids
    auteur
    Emmanuel Abbe, Laurent Massoulié, Andrea Montanari, Allan Sly, Nikhil Srivastava
    article
    Mathematical Statistics and Learning, EMS Publishing House, 2018
    Accès au bibtex
    https://arxiv.org/pdf/1706.08561 BibTex
    titre
    Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs
    auteur
    Charles Bordenave, Marc Lelarge, Laurent Massoulié
    article
    Annals of Probability, Institute of Mathematical Statistics, 2018, 46 (1), pp.1-71
    Accès au bibtex
    BibTex

    Pré-publication, Document de travail

    titre
    Accelerated decentralized optimization with local updates for smooth and strongly convex objectives
    auteur
    Hadrien Hendrikx, Francis Bach, Laurent Massoulié
    article
    2018
    Accès au texte intégral et bibtex
    https://hal.inria.fr/hal-01893568/file/1810.02660.pdf BibTex

    2017

    Article dans une revue

    titre
    A spectral method for community detection in moderately sparse degree-corrected stochastic block models
    auteur
    Lennart Gulikers, Marc Lelarge, Laurent Massoulié
    article
    Advances in Applied Probability, Applied Probability Trust, 2017, 49 (03), pp.686 – 721. ⟨10.1017/apr.2017.18⟩
    Accès au bibtex
    BibTex

    Communication dans un congrès

    titre
    Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
    auteur
    Lennart Gulikers, Marc Lelarge, Laurent Massoulié
    article
    ITCS 2017 – 8th Innovations in Theoretical Computer Science, Jan 2017, Berkeley, United States. pp.1-52
    Accès au bibtex
    https://arxiv.org/pdf/1609.02487 BibTex
    titre
    Adaptive Matching for Expert Systems with Uncertain Task Types
    auteur
    Virag Shah, Lennart Gulikers, Laurent Massoulié, Milan Vojnovic
    article
    Allerton 2017 – 55th Annual Allerton Conference on Communication, Control, and Computing, Oct 2017, Monticello, IL, United States
    Accès au bibtex
    https://arxiv.org/pdf/1703.00674 BibTex
    titre
    Rapid Mixing of Local Dynamics on Graphs
    auteur
    Laurent Massoulié
    article
    31st International Symposium on Distributed Computing (DISC 2017), Oct 2017, Vienna, Austria
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-01940437/file/BA_DISC_2017.pdf BibTex

    Pré-publication, Document de travail

    titre
    Optimal algorithms for smooth and strongly convex distributed optimization in networks
    auteur
    Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, Laurent Massoulié
    article
    2017
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-01478317/file/distributed_dual_axiv.pdf BibTex

    2016

    Communication dans un congrès

    titre
    Social Clicks: What and Who Gets Read on Twitter?
    auteur
    Maksym Gabielkov, Arthi Ramachandran, Augustin Chaintreau, Arnaud Legout
    article
    ACM SIGMETRICS / IFIP Performance 2016, Jun 2016, Antibes Juan-les-Pins, France
    Accès au texte intégral et bibtex
    https://hal.inria.fr/hal-01281190/file/sigm095-gabielkov.pdf BibTex
    titre
    A utility optimization approach to network cache design
    auteur
    Mostafa Dehghan, Laurent Massoulié, Don Towsley, Daniel Sadoc Menasche, Yong Chiang Tay
    article
    IEEE INFOCOM 2016 – The 35th Annual IEEE International Conference on Computer Communications, Apr 2016, San Francisco, United States. ⟨10.1109/INFOCOM.2016.7524445⟩
    Accès au bibtex
    BibTex
    titre
    On the capacity of information processing systems
    auteur
    Laurent Massoulié, Kuang Xu
    article
    29th Annual Conference on Learning Theory, Jun 2016, New York, United States
    Accès au bibtex
    BibTex

    Pré-publication, Document de travail

    titre
    A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
    auteur
    Lennart Gulikers, Marc Lelarge, Laurent Massoulié
    article
    2016
    Accès au bibtex
    https://arxiv.org/pdf/1506.08621 BibTex
    titre
    An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model
    auteur
    Lennart Gulikers, Marc Lelarge, Laurent Massoulié
    article
    2016
    Accès au bibtex
    https://arxiv.org/pdf/1511.00546 BibTex

    2015

    Article dans une revue

    titre
    The Price of Privacy in Untrusted Recommender Systems
    auteur
    Siddhartha Banerjee, Nidhi Hegde, Laurent Massoulié
    article
    IEEE Journal of Selected Topics in Signal Processing, IEEE, 2015, IEEE Journal of Topics in Signal Processing,, 9 (7), pp.1319 – 1331. ⟨10.1109/JSTSP.2015.2423254⟩
    Accès au bibtex
    BibTex
    titre
    Self-Organizing Flows in Social Networks
    auteur
    Nidhi Hegde, Laurent Massoulié, Laurent Viennot
    article
    Theoretical Computer Science, Elsevier, 2015, pp.16. ⟨10.1016/j.tcs.2015.02.018⟩
    Accès au texte intégral et bibtex
    https://hal.inria.fr/hal-00761046/file/flow_social.pdf BibTex
    titre
    From Small-World Networks to Comparison-Based Search
    auteur
    Amin Karbasi, Stratis Ioannidis, Laurent Massoulié
    article
    IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, 61 (6), pp.19. ⟨10.1109/TIT.2015.2418284⟩
    Accès au bibtex
    BibTex

    Communication dans un congrès

    titre
    Fast and Memory Optimal Low-Rank Matrix Approximation
    auteur
    Yun Se-Young, Marc Lelarge, Alexandre Proutière
    article
    NIPS 2015, Dec 2015, Montreal, Canada
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-01254913/file/5929-fast-and-memory-optimal-low-rank-matrix-approximation.pdf BibTex
    titre
    On the Interaction between Content Caching and Request Assignment in Cellular Cache Networks
    auteur
    Kolar Purushothama Naveen, Laurent Massoulié, Emmanuel Baccelli, Aline Carneiro Viana, Don Towsley
    article
    AllThingsCellular ’15 – 5th Workshop on All Things Cellular: Operations, Applications and Challenges , Aug 2015, Londres, United Kingdom. ⟨10.1145/2785971.2785975⟩
    Accès au texte intégral et bibtex
    https://hal.inria.fr/hal-01244774/file/Author-Generated-version.pdf BibTex
    titre
    Clustering and Inference From Pairwise Comparisons
    auteur
    Wu Rui, Jiaming Xu, Srikant Rayadurgam, Marc Lelarge, Laurent Massoulié, Bruce Hajek
    article
    SIGMETRICS ’15 Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2015, Portland, United States. pp.2, ⟨10.1145/2796314.2745887⟩
    Accès au bibtex
    BibTex
    titre
    Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
    auteur
    Charles Bordenave, Marc Lelarge, Laurent Massoulié
    article
    2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Oct 2015, Berkeley, United States. ⟨10.1109/FOCS.2015.86⟩
    Accès au bibtex
    BibTex
    titre
    Greedy-Bayes for Targeted News Dissemination
    auteur
    Laurent Massoulié, Alexandre Proutière, Mesrob Ohannessian
    article
    SIGMETRICS ’15 Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Jun 2015, Portland, United States. pp.12, ⟨10.1145/2745844.2745868⟩
    Accès au bibtex
    BibTex
    titre
    Designing Adaptive Replication Schemes in Distributed Content Delivery Networks
    auteur
    Mathieu Leconte, Marc Lelarge, Laurent Massoulié
    article
    Teletraffic Congress (ITC 27), 2015 27th International, 2015, Ghent, Belgium. ⟨10.1109/ITC.2015.11⟩
    Accès au bibtex
    BibTex
    titre
    Speeding up Glauber Dynamics for Random Generation of Independent Sets
    auteur
    Rémi Varloot, Ana Busic, Anne Bouillard
    article
    2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems , Jun 2015, Portland, United States. pp.461-462, ⟨10.1145/2745844.2745893⟩
    Accès au bibtex
    BibTex

    2014

    Article dans une revue

    titre
    Distributed user profiling via spectral methods
    auteur
    Dan-Cristian Tomozei, Laurent Massoulié
    article
    Stochastic Systems, INFORMS Applied Probability Society, 2014, 4, pp.1-43. ⟨10.1214/11-SSY036⟩
    Accès au bibtex
    BibTex
    titre
    Distributed Content Curation on the Web
    auteur
    Zeinab Abbassi, Nidhi Hegde, Laurent Massoulié
    article
    ACM Transactions on Internet Technology, Association for Computing Machinery, 2014, pp.9. ⟨10.1145/2663489⟩
    Accès au bibtex
    BibTex

    Communication dans un congrès

    titre
    Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
    auteur
    Jiaming Xu, Laurent Massoulié, Marc Lelarge
    article
    Conference on Learning Theory, Jun 2014, Barcelona, Spain. pp.903-920
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-01066047/file/GeneralizedSBM_COLT_final.pdf BibTex
    titre
    Community detection thresholds and the weak Ramanujan property
    auteur
    Laurent Massoulié
    article
    STOC 2014: 46th Annual Symposium on the Theory of Computing, Jun 2014, New York, United States. pp.1-10
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-00969235/file/rama_final.pdf BibTex
    titre
    Streaming, Memory Limited Algorithms for Community Detection
    auteur
    Se-Young Yun, Marc Lelarge, Alexandre Proutière
    article
    NIPS 2014, Dec 2014, Montreal, Canada
    Accès au bibtex
    https://arxiv.org/pdf/1411.1279 BibTex

    2013

    Article dans une revue

    titre
    Optimal Control of End-User Energy Storage
    auteur
    Laurent Massoulié, Peter van de Ven, Nidhi Hegde, Theodoros Salonidis
    article
    IEEE Transactions on Smart Grid, Institute of Electrical and Electronics Engineers, 2013, 4 (2), pp.789-797. ⟨10.1109/TSG.2012.2232943⟩
    Accès au bibtex
    BibTex
    titre
    The role of coding in the choice between routing and coding for wireless unicast
    auteur
    Ramakrishna Gummadi, Laurent Massoulié, Ramavarapu Sreenivas
    article
    Physical Communication, 2013, 6, pp.88-99. ⟨10.1016/j.phycom.2012.05.004⟩
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-00969182/file/phycom_revised.pdf BibTex
    titre
    Optimal Content Placement for Peer-to-Peer Video-on-Demand Systems.
    auteur
    Laurent Massoulié, Bo Tan
    article
    IEEE/ACM Transactions on Networking, IEEE/ACM, 2013, 21 (2), pp.566-579. ⟨10.1109/TNET.2012.2208199⟩
    Accès au bibtex
    BibTex

    Communication dans un congrès

    titre
    Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing.
    auteur
    Mathieu Leconte, Marc Lelarge, Laurent Massoulié
    article
    SODA 2013 – ACM-SIAM Symposium on Discrete Algorithms, Jan 2013, United States. p. 35-46
    Accès au texte intégral et bibtex
    https://hal.archives-ouvertes.fr/hal-00827810/file/0236-000088_Paper.pdf BibTex
    titre
    Reconstruction in the Labeled Stochastic Block Model
    auteur
    Marc Lelarge, Laurent Massoulié, Jiaming Xu
    article
    IEEE Information Theory Workshop, Sep 2013, Seville, Spain
    Accès au bibtex
    BibTex
    titre
    Self-organizing Flows in Social Networks
    auteur
    Nidhi Hegde, Laurent Massoulié, Laurent Viennot
    article
    Structural Information AND Communication Complexity – 20th International Colloquium, SIROCCO, Jul 2013, Ischia, Italy. pp.116-128
    Accès au bibtex
    BibTex
    titre
    How to Optimally Allocate Your Budget of Attention in Social Networks
    auteur
    Bo Jiang, Nidhi Hegde, Laurent Massoulié, Don Towsley
    article
    IEEE INFOCOM 2013 – IEEE Conference on Computer Communications, Apr 2013, Torino, Italy
    Accès au texte intégral et bibtex
    https://hal.inria.fr/hal-00839599/file/1569648953.pdf BibTex
    titre
    Stable and scalable universal swarms
    auteur
    Laurent Massoulié, Ji Zhu, Stratis Ioannidis, Nidhi Hegde
    article
    Proceedings of the 2013 ACM symposium on Principles of distributed computing, 2013, United States. pp.260-269, ⟨10.1145/2484239.2484272⟩
    Accès au bibtex
    BibTex

    2006

    Article dans une revue

    titre
    A Queueing Analysis of Max-Min Fairness, Proportional Fairness and Balanced Fairness
    auteur
    Thomas Bonald, Laurent Massoulié, Alexandre Proutière, Jorma Virtamo
    article
    Queueing Systems, Springer Verlag, 2006, ⟨10.1007/s11134-006-7587-7⟩
    Accès au texte intégral et bibtex
    https://hal.inria.fr/hal-01244245/file/questa06.pdf BibTex