Jean-Baptiste Rouquier , Institut des Systèmes Complexes

Location :

LIP6
Site Passy-Kennedy
104 avenue du Président Kennedy 75016 Paris
Salle 847

Abstract :

In many networks, vertices have hidden attributes that are correlated with the network’s topology. 
For instance, in social networks, people are more likely to be friends if they are demographically 
similar. In food webs, predators typically eat prey of lower body mass. We explore a setting in 
which the network’s topology is known, but these attributes are not. If each vertex can be queried, 
learning the value of its hidden attributes — but only at some cost — then we need an algorithm 
which chooses which vertex to query next, in order to learn as much as possible about the 
attributes of the remaining vertices. We assume that the network is generated by a probabilistic 
model, but we make no assumptions about the assortativity or disassortativity of the network. We 
then query the vertex with the largest mutual information between its type and that of the others 
(a well-known approach in active learning) or with the largest average agreement between two 
independent samples of the Gibbs distribution which agree on its type. We test these 
approaches on two networks with known attributes, the Karate Club network and a food 
web of species in the Weddell Sea. In several cases, we found that the average agreement 
algorithm performs better than mutual information, and both perform better than simpler heuristics. 
The algorithms appear to explore the network intelligently, first querying vertices at the centers 
of communities, and then vertices along the boundaries between communities.

Host :

ComplexNetworks (LIP6)