Data Science and Machine Learning

Topics

Detecting planted communities in random graphs

The stochastic block model (aka. planted partition model) is a popular model for representing networks with communities. Elchanan Mossel, Joe Neeman, and Allan Sly have been investigating algorithms and fundamental limits for detecting and recovering these communities. They established sharp transitions for the problem of extracting non-trivial information and the problem of exactly recovering communities. They also gave a new algorithm that obtains provably optimal accuracy for the problem of detecting communities in “Consistency thresholds for the planted bisection model” and “Belief propagation, robust reconstruction, and optimal recovery of block models“.

Mathematics of social networks

Avhishek Chatterjee, François Baccelli and Sriram Vishwanath proposed a stochastic extension of the bounded confidence model where opinions take their values in the Euclidean space and where friendship and interactions are dynamically defined through time varying and random neighborhoods. Two basic sub-models are defined: the influencing model where each agent is an attractor to the opinions of its neighbors and the listening model where each agent gathers information from others to update its own opinions. The general model contains a rich set of variants for which they proposed a classification. They analyzed the stability of its dynamics. The analysis highlights the need of certain leaders with heavy tailed neighborhoods for stability to hold.

Members

Jae Oh Woo

Department of Mathematics and Department of Electrical and Computer Engineering, UT Austin
jaeoh.woo@utexas.edu
Read More »

Rachel Ward

Department of Mathematics, UT Austin
rward@math.utexas.edu
Read More »

Anastasios Kyrillidis

Department of Electrical and Computer Engineering, UT Austin
anastasios@utexas.edu
Read More »

Constantine Caramanis

Department of Electrical and Computer Engineering, UT Austin
constantine@utexas.edu
512 471 9269
Read More »

Sujay Sanghavi

Department of Electrical and Computer Engineering, UT Austin
sanghavi@mail.utexas.edu
512 475 9798
Read More »

Sanjay Shakkottai

Department of Electrical and Computer Engineering, UT Austin
shakkott@austin.utexas.edu
512 471 5376
Read More »

Joe Neeman

Department of Electrical and Computer Engineering and Department of Mathematics, UT Austin
joeneeman@gmail.com
Read More »

Abishek Sankararaman

Department of Electrical and Computer Engineering, UT Austin
abishek@utexas.edu
Read More »

Avhishek Chatterjee

Department of Electrical and Computer Engineering, UT Austin
avhishek@utexas.edu
Read More »

Sriram Vishwanath

Department of Electrical and Computer Engineering, UT Austin
sriram@ece.utexas.edu
512 471 1190
Read More »

Gustavo de Veciana

Department of Electrical and Computer Engineering, UT Austin
gustavo@ece.utexas.edu
512 471 1573
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
baccelli@math.utexas.edu
512 471 17 54
Read More »

Publications

2014-06-18_1000333

Belief propagation, robust reconstruction, and optimal recovery of block models

Elchanan Mossel, Joe Neeman and Allan Sly Conference on Learning Theory 2014
Download PDF
2015-06-16_1000329

Consistency thresholds for the planted bisection model

Elchanan Mossel, Joe Neeman and Allan Sly To appear in Symposium on the Theory of Computer Science 2015
Download PDF
2015-04-30_1000324

Pairwise Stochastic Bounded Confidence Opinion Dynamics: Heavy Tails and Stability

François Baccelli, Avhishek Chatterjee and Sriram Vishwanath Proceedings IEEE Infocom 2015