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)

2020

Communication dans un congrès

titre
Dual-Free Stochastic Decentralized Optimization with Variance Reduction
auteur
Hadrien Hendrikx, Francis Bach, Laurent Massoulié
article
NeurIPS 2020 – 34th Conference on Neural Information Processing Systems, Dec 2020, Vancouver / Virtual, Canada
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02974237/file/DVR_camera_ready_supp.pdf BibTex
titre
Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
auteur
Hadrien Hendrikx, Lin Xiao, Sébastien Bubeck, Francis Bach, Laurent Massoulié
article
ICML 2020 – Thirty-seventh International Conference on Machine Learning, Jul 2020, Vienna / Virtual, Austria
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02974232/file/MSR_visit.pdf BibTex

Direction d’ouvrage, Proceedings, Dossier

titre
From tree matching to sparse graph alignment
auteur
Luca Ganassali, Laurent Massoulié
article
ML Research Press, 2020
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02941092/file/0_main_article.pdf BibTex

Pré-publication, Document de travail

titre
Probabilistic and mean-field model of COVID-19 epidemics with user mobility and contact tracing
auteur
Marianne Akian, Luca Ganassali, Stéphane Gaubert, Laurent Massoulié
article
2020
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02941123/file/multi-type_branching_merge_v1.pdf BibTex
titre
Spectral alignment of correlated Gaussian random matrices
auteur
Luca Ganassali, Marc Lelarge, Laurent Massoulié
article
2020
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02941069/file/Spectral_alignment_of_correlated_Gaussian_matrices.pdf BibTex
titre
Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area
auteur
Stéphane Gaubert, Marianne Akian, Xavier Allamigeon, Marin Boyet, Baptiste Colin, Théotime Grohens, Laurent Massoulié, David Parsons, Frederic Adnet, Érick Chanzy, Laurent Goix, Frédéric Lapostolle, Éric Lecarpentier, Christophe Leroy, Thomas Loeb, Jean-Sébastien Marx, Caroline Télion, Laurent Treluyer, Pierre Carli
article
2020
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02648075/file/arxivv2.pdf BibTex

2019

Article dans une revue

titre
A Utility Optimization Approach to Network Cache Design
auteur
Mostafa Dehghan, Laurent Massoulié, Don Towsley, Daniel Sadoc Menasche, Yong Chiang Tay
article
IEEE/ACM Transactions on Networking, IEEE/ACM, 2019, 27 (3), pp.1013-1027. ⟨10.1109/TNET.2019.2913677⟩
Accès au bibtex
BibTex
titre
Rapid Mixing of Dynamic Graphs with Local Evolution Rules
auteur
Laurent Massoulié, Rémi Varloot
article
IEEE Transactions on Network Science and Engineering, IEEE, 2019, pp.1. ⟨10.1109/TNSE.2019.2926887⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02427853/file/ieee-author-final.pdf BibTex
titre
Efficient inference in stochastic block models with vertex labels
auteur
Clara Stegehuis, Laurent Massoulié
article
IEEE Transactions on Network Science and Engineering, IEEE, 2019, pp.1. ⟨10.1109/TNSE.2019.2913949⟩
Accès au bibtex
BibTex
titre
Optimal Convergence Rates for Convex Distributed Optimization in Networks
auteur
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Lee, Laurent Massoulié
article
Journal of Machine Learning Research, Microtome Publishing, 2019, 20, pp.1 – 31
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02440504/file/scaman_optimal_convergence.pdf BibTex

Communication dans un congrès

titre
An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
auteur
Hadrien Hendrikx, Francis Bach, Laurent Massoulié
article
Neural Information Processing systems, Dec 2019, Vancouver, Canada
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02280763/file/1905.11394.pdf BibTex
titre
Planting trees in graphs, and finding them back
auteur
Laurent Massoulié, Ludovic Stephan, Don Towsley
article
COLT 2019 – Conference on Learning Theory, Jun 2019, Phoenix, United States
Accès au bibtex
https://arxiv.org/pdf/1811.01800 BibTex
titre
Accelerated decentralized optimization with local updates for smooth and strongly convex objectives
auteur
Hadrien Hendrikx, Francis Bach, Laurent Massoulié
article
AISTATS 2019 – 22nd International Conference on Artificial Intelligence and Statistics, Apr 2019, Naha, Okinawa, Japan
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01893568/file/Accelerated_decentralized_optimization_with_local_updates.pdf BibTex
titre
Robustness of spectral methods for community detection
auteur
Ludovic Stephan, Laurent Massoulié
article
COLT 2019 – Conference on Learning Theory, Jun 2019, Phoenix, United States
Accès au bibtex
https://arxiv.org/pdf/1811.05808 BibTex

2018

Article dans une revue

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
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
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
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

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
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
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

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
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
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

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
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
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

Communication dans un congrès

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
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
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
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
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
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
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
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
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

2013

Article dans une revue

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
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, Elsevier, 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 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

Communication dans un congrès

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
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
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
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

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