Programs & Events

programs

Yale-led project connects social networks and the microbiome

YINS
January 17, 2019

Can our gut bacteria influence our social status and popularity? This is one of the many questions that the Yale Human Nature Lab is investigating in a new project that studies the relationship between human social networks and the microbiome.

Led by Nicholas Christakis, Yale’s Sterling Professor of social and natural science and the director of the Human Nature Lab, the Microbiome Biology and Social Networks in the Developing World project launched Jan. 1. The project is funded by a $3.54 million grant from the NOMIS Foundation and will take place in the Copan region of Honduras.

The project will build on work the Human Nature Lab has conducted in the region for the past five years. In this work, the lab is constructing the largest mapping of face-to-face networks. Using a software called Trellis, which was developed for this project, the lab selected villages within the region and photographed every member of the village. The lab asked those surveyed to identify members of their network, such as friends, relatives and neighbors, using the data to construct network maps.

“A social network is a hyperdimensional surface, and we believe that bacteria evolve to occupy particular spots within social networks,” Christakis said. “For example, the kinds of bacteria in the guts of popular people should be different than the bacteria in the guts of unpopular people. Bacteria flow within our social fabric and have preferred locations.”

According to Christakis, the parent project was funded by a grant from the Bill and Melinda Gates Foundation and supported by the TATA Group. The parent grant focused on creating “artificial tipping points” in villages to change attitudes toward infant mortality and maternal morbidity. The project constructed social network maps to identify the most influential individuals in a community — those who, if they adopted an intervention, could lead to an entire village adopting an intervention.

In this new project, the lab will continue to construct social network maps, and will also collect stool and spit samples from more than 3,000 of the 30,000 participants in the project. Christakis expects the project to take several years and explained that all samples collected will need to be analyzed for their bacterial species. After the initial analysis, all bacteria will be genotyped, and further data analysis will continue from there.

Conducting a project of this scale in a developing country like Honduras is not without its difficulties, according to Christakis. He added that liquid nitrogen and freezers — equipment that are necessary for preserving the bacteria in the samples — are difficult to locate in Honduras.

John Lee ’19, who works for the Human Nature Lab, explained that he experienced technical difficulties during a recent trip to Honduras for the project. While visiting the field site in December, Lee was responsible for transporting a container for collected samples. Even though he spoke with transportation officials to ensure that the container could travel through an airport, he underwent significant questioning in regard to his intentions. After the transportation ordeal, the dry shipper was nonfunctional upon arrival in Honduras.

Still, Lee, who has worked in the Human Nature Lab since spring of 2015, expressed his excitement for the new microbiome project.

“We were really excited to get the grant,” he said. “The lab employs local surveyors and has a huge impact on the community in Honduras. I’m happy that we can expand our research, further community engagement and keep our employment commitment to the people we work with in Honduras.”

Libby Henry ’17, a student who began working in the Human Nature Lab in the summer of 2015 and who continues to consult, expressed her enthusiasm for the project. The project is an opportunity to draw from a number of different fields and to learn something new, she said.

The Human Nature Lab sits within the Yale Institute for Network Science.

External link: 

“Dynamic control of spreading processes on networks”

Speaker: Soheil Eshghi, Ph.D.
Postdoc, Crawford Lab

Event time: 
Wednesday, January 23, 2019 - 12:00pm
Event Type: 
Weekly Seminar
Location: 
Yale Institute for Network Science See map
17 Hillhouse Avenue, Room 328
New Haven, CT 06511
Amin Karbasi

Better living through algorithms

YINS
December 13, 2018

This story originally appeared in Yale Engineering magazine.

Whether you’re figuring out the best place to catch an Uber ride or mapping the human brain, there’s a better, faster way to do it. Amin Karbasi, assistant professor of electrical engineering and computer science, is working on it.

Working at the intersection of learning theory, optimization, and information processing, Karbasi’s research focuses on developing ways to better navigate our increasingly data-filled world. There’s a greater need than ever for this kind of research. Thanks to the Internet and social media in particular, a tremendous amount of data is generated every second by millions of users. Every minute Instagram users post nearly 220,000 new photos, YouTube users upload 72 hours of video, and Facebook users share nearly 2.5 million pieces of content.

“It’s no secret that data’s getting bigger and bigger, and one way or another, we need to deal with that,” said Karbasi, who is also a faculty member at the Yale Institute for Network Science.

How we organize and make sense of all this information is an ongoing challenge in computing. In many cases, he said, we just discard the data. It’s easy, but not the best way to deal with it. Using data-driven algorithms and other techniques, such as summarization methods that find the right representative subset to get a clear picture of the whole set, Karbasi wants to find a better way. One approach is sampling.

“You have a huge amount of data and you want to sample the most important points,” said Karbasi, who was listed this year by the prestigious International Conference on Machine Learning as one the most prolific researchers in the field. “If you sample and find the most important points, you’re going to have a much smaller data set, but hopefully the quality is going to be similar.”

Speed vs. accuracy

Much of Karbasi’s work involves finding the sweet spot between accuracy and speed in data searches. In each case, they need to figure out how comprehensive the list needs to be.“Do you want to be exact or do you want to be fast? You can’t have both,” Karbasi said. “That’s the trade-off. In medical applications, you want to be really accurate, but in mundane mission-learning applications, deciding if this image is a cat or a dog — the stakes are lower — I can make mistakes once in a while. But if it’s a doctor trying to tell whether it’s a tumor or not, you have to be very, very careful.”

Once they assess the proper speed/accuracy ratio, Karbasi and his research team can develop the right methods for extracting the data. “Tell me how much wiggle room I have and I can tell you how fast I can compute,” he said.Karbasi’s work is filled with high-level mathematics, seemingly endless equations and many abstract concepts. But the results play out in some of the most everyday ways — a better online system for making movie recommendations, for instance, or finding the best place to catch a ride. A recent study of his aimed to create the most efficient system for finding waiting locations for an Uber.A person sitting at a computer with two monitors displaying an array of movie choices on Netflix.(Photo credit: Daniel Krason via Shutterstock)“If you’re in Manhattan, every centimeter, ever corner can be a pickup location,” he said. “The question is which corner should I pick?”

For this, a mathematical strategy known as discrete optimization, comes into play.“You have 10 million data points in front of you but you want to choose only 100 of those,” he said. “If you want to find the representative points or intelligently summarize the data, you have to maximize these discrete functions. Our group has focused a lot on the discrete optimization problems — how fast and accurate we can compute them.”

A fully comprehensive algorithm that factors in every street corner would take a prohibitively long time to compute. But an algorithm that takes only a few seconds to provide results would likely be welcomed by consumers, even if it required them to to walk a block to catch their rides. Throughout the year, the best spots change — areas near ice rinks are popular in winter, for instance. A way to update the best locations each day would be invaluable to the company.

To find the optimum waiting spots for Uber drivers, Karbasi and his fellow researchers analyzed a dataset of 100,000 Uber pickups in Manhattan from April 2014 (just a fraction of potential pickup locations in Manhattan). They developed an algorithm that reduces the set of 100,000 to 30 spots representative of the larger set, and then chooses three different waiting locations withineach region.

And if you get antsy waiting for a ride, try completely mapping the neural connections in the human brain — an endeavor estimated to take some 14 billion years. That is (obviously) a long time, but identifying the topology of the brain’s network could tell us a lot about the physiological basis for how we process information. Fortunately, Karbasi is working on other less time-consuming methods to do so.

Working with researchers from the Ecole Polytechnique Federale de Lausanne in Switzerland, Karbasi helped develop an algorithm that scales to large datasets of recorded neural activities. By mathematically analyzing this mapping, the researchers could tell the conditions under which the algorithm successfully identified the type of synaptic connections within the available data.

Another brain-related study brought Karbasi in collaboration with two other researchers at Yale, Todd Constable and Dustin Scheinost in the departments of neurosurgery and radiology and biomedical imaging. The researchers analyzed the fMRI scans of more than 100 subjects from the Human Connectome Project, a five-year effort to create a network map of the human brain. Doing so allowed them to develop a method of analyzing the neuronal connections of individual brains that allow them to successfully predict the subjects’ IQs, their sex, and even tasks they were performing at the time of the brain scan.

The researchers focused on what’s known as voxels. Analogous to a pixel, a voxel is the lowest resolution achievable in the scans, and each can represent up to millions of neurons. Researchers cluster voxels into different areas called nodes or parcels, a process known as parcellating. A universal atlas of the brain has been developed through traditional methods of parcellating the brain, but these methods don’t factor the many inter-individual variations and the unique nature of the neural connections. Because a single functional atlas may not apply to all individuals or conditions, these variations are particularly important for patient and developmental studies.

“Traditional approaches to human brain parcellation collapse data from all the subjects in the group and then they cluster the average,” said Mehraveh Salehi, a Ph.D. candidate in the the labs of both Constable and Karbasi. “But we’ve shown that if you do this at the individual level, each individual has a different parcellation.”

To individualize the existing parcellations, the team used a method of summarizing large amounts of data known as exemplar-based clustering, which seeks the most representative elements of the data.

“If we account for those variations, we can build up better models from the functional connectivity analysis, and those models are better at predicting behaviors, such as IQ,” she said.

Karbasi said it was remarkable how much information they could get from the network of voxels.

“What was very fascinating was that the shape of the network tells a lot of stories,” Karbasi said. “For example, we can say whether this person in the scanner is a male or a female. It also tells us that these people are performing different types of tasks. It’s like reading the brain.”

He added that they’re just “scratching the surface” of the technology’s potential.

“Just imagine what we might do in 20 years if we can really read the brain, and understand what people are thinking,” Karbasi said. For example, he said, it could potentially lead to a better understanding of how the brain makes the transition from one emotional state to another and new treatments for depression.

In focusing on these problems, Karbasi’s group needs to factor in which platforms they’re designing their solutions. For instance, a typical home computer has a much more limited capacity than a company such as Google, which has massive computing power. So it makes sense that the Internet search giant has sought Karbasi’s expertise. His upcoming sabbatical will be spent doing research for the company, which recently awarded him with funding to help turn the tens of millions of data points into something manageable. One method Karbasi is looking at involves choosing elements from a particular dataset that fall into a category, but aren’t overly similar.

“We are trying to come up with algorithms that can do this kind of thing fast,” he said. “What we do is we represent every image by a data point, or a vector, and then we can define distances between the vectors.” He compares the data points to molecules of a gas — they’re far from each other, but fill the entire space.

To do this, Karbasi’s research team applied their method on a publicly available dataset, called “tiny images,” which contains 80 million images crawled from the web. “What we wanted to do was summarize this data — if you want to pick 100 images, which ones? We came up with algorithms that can do this very fast.”

They developed a distributed algorithm that chops the data into small pieces so that each piece can be performed on a single computer. “And then we merge the results, and do something intelligent with them,” he said.

Using classical algorithms would take an extremely long time to essentially perform the same task. Using his algorithms, the computers in his lab finished in only a few hours. Google — with all of its resources — might take only a few seconds.

Karbasi’s work has made him a sought-after expert. In addition to Google, the U.S. Air Force and Microsoft are among those to have also funded his research. He recently completed an online training program for the Defense Advanced Research Projects Agency (DARPA) that aims to create a better data-driven online education system that interacts with humans. Recruiting subjects from Amazon’s Mechanical Turk platform, the test trains users to distinguish between three types of woodpeckers.

As part of the test, users try to identify a specific bird and then receive another example based on that answer. The system monitors the responses and adjusts its teaching approach to the test taker’s learning style. While computer training programs often take a “one size fits all” approach, Karbasi’s program personalizes massive online courses. The general idea behind the test has applications well beyond wildlife.

“At DARPA, they need to know ‘Is this person OK, is this person not OK?’” Karbasi said. “It’s very hard for people to read and understand the cues, so they want an automated machine learning system that learns about humans.”

From our mundane tasks to critical medical procedures, data is becoming ever more present in our lives and serves as a common thread through seemingly disparate problems. Karbasi is among the researchers making the daunting amount of information a little more manageable.

“These are all very different applications, but at end of day, these are the same problems — and we can solve them,” he said.  

External link: 

”Positive Semidefiniteness of Laplacian Matrices of Signed Networks”

Speaker: Ji Liu
Assistant Professor, Stony Brook University

Event time: 
Tuesday, December 11, 2018 - 1:00pm
Event Type: 
Speakers, Conferneces & Workshops
Location: 
Room 514, Dunham Lab See map
10 Hillhouse Avenue
New Haven, CT 06520

“Modelling and Analysis of Opinion Dynamics on Social Networks”

Speaker: Mengbin Ye
Postdoctoral Fellow, University of Groningen 

Event time: 
Monday, December 10, 2018 - 3:00pm
Event Type: 
Speakers, Conferneces & Workshops
Location: 
Room 514, Dunham Lab See map
10 Hillhouse Avenue
New Haven, CT 06520

“Local flow-based methods for graph clustering”

Speaker: Di Wang
Postdoc, Georgia Tech

Event time: 
Friday, December 7, 2018 - 2:00pm
Event Type: 
Speakers, Conferneces & Workshops
Location: 
Yale Institute for Network Science See map
17 Hillhouse Avenue, Room 335
New Haven, CT 06511

“So Many Choices, So Little Time: Learning from Comparison and Rank Data”

Speaker: Prof. Matthias Grossglauser
Information and Network Dynamics group
School of Computer and Communication Sciences, EPFL

Event time: 
Wednesday, December 5, 2018 - 12:00pm
Event Type: 
Weekly Seminar
Location: 
Yale Institute for Network Science See map
17 Hillhouse Ave, 3rd floor
New Haven, CT 06511
Dragomire Radev

Dragomir Radev named AAAS Fellow

YINS
November 27, 2018

Four Yale faculty members have been named fellows of the American Association for the Advancement of Science (AAAS), an honor bestowed upon AAAS members by their peers.

The awardees are: Charles H. Ahn, the William K. Lanman Jr. Professor of Applied Physics and chair of the Department of Applied Physics; Richard Bribiescas, professor of anthropology and ecology and evolutionary development and deputy provost for faculty development and diversity; Christopher G. Burd, professor and deputy chair of cell biology; and Dragomir Radev, the A. Bartlett Giamatti Professor of Computer Science.

Dragomir Radev was honored for his distinguished contributions to the fields of natural language processing, information retrieval, and artificial intelligence.

Radev has served as secretary of the Association for Computational Linguistics, is co-founder of the North American Computational Linguistics Olympiad, and is a fellow of the Association for Computing Machinery.

The new fellows will be presented with an official certificate and a gold and blue (representing science and engineering, respectively) rosette pin on Feb. 16 at the 2019 AAAS Annual Meeting in Washington, D.C.

This year’s AAAS Fellows will be formally announced in the AAAS News & Notes section of the journal Science on Nov. 29.

The AAAS is the world’s largest general scientific society and publisher of the journal Science, as well as Science Translational Medicine; Science Signaling, a digital, open-access journal; Science Advances; Science Immunology; and Science Robotics. It was founded in 1848 and includes nearly 250 affiliated societies and academies of science, serving 10 million individuals.

External link: 

“Opportunities for Statistics in Implementation Science at Yale’s new Center for Methods in Implementation and Prevention Science (CMIPS)”

Speaker: Donna Spiegelman
Yale University

Event time: 
Monday, October 29, 2018 - 4:15pm
Event Type: 
Speakers, Conferneces & Workshops
Location: 
Yale Institute for Network Science See map
17 Hillhouse Avenue, 3rd floor
New Haven, CT 06511

“Federated Machine Learning in Resource-Constrained Edge Computing Systems”

Speaker: Shiqiang Wang, Ph.D.
IBM T.J. Watson Research Center 

Event time: 
Tuesday, October 30, 2018 - 10:00am
Event Type: 
Weekly Seminar
Location: 
Yale Institute for Network Science See map
17 Hillhouse Avenue, Room 335
New Haven, CT 06511

Pages

Subscribe to programs