Inference on random graph, with an application to mobile sensors I've attended a course on Machine Learning and another one in Network Analysis, and I wonder if this two topics already intersect, in particular I'm interested in the following model:


*

*we have a mobile network (that is, the nodes perform a random walk in some area, then sending a message within some assigned range, let's say with radius r, communicating with every other node that in that moment is in that range).

*we take the point of view of a node and would like to infer as much as we can about the whole network (under suitable assumption, for example knowing or not knowing the total number of nodes, etc.), possibly in order to perform some achieved probabilistic version of well known distributed algorithm.


Are there results with respect to this scenario?
 A: Interesting problem.  
If we assume that each message exchanged between pairs of nodes contain summary information about every other exchange that has happened, for example, ID and status or ID and last known location.  
In that case, any single node will have access to information about other nodes, and the number of nodes that any node has information on will increase as a function of time.
The closest analogy to this is from statistical mechanics, where over time, the number of collisions between distinct particles increases, to the point where with probability 1, every node has some (perhaps out of date) information about every other node.
A: Two years ago I asked this question investigating distributed algorithms that infers properties of the underlying network in the mobile network model. 
I was interested mainly on analytical results; it turned out that there's no much mathematical theory about making inference on mobile networks in a distributed fashion. At the best of my knowledge, I can point to some related problems and results.
In the broader context of dynamic graphs (graphs that change their topology as time passes), an hot topic is that of Distributed Community Detection.
My research group has published the first analytical result about this problem (at the best of my knowledge). The idea is that one can design a simple and lightweight distributed algorithm that identifies the "clusters" of "more-probably-connected" nodes. However, that result is valid on a natural dynamic version of the well known Planted Bisection Model, not on mobile networks (so, here's an open problem).
For more details, please refer to the cited paper.
Another interesting and important problem is that of Distributed Majority Consensus. Here, each node initially holds an opinion, and we need a distributed and lightweight algorithm (in terms of the node's memory) that makes all nodes rapidly converge to the initial "plurality opinion". In that context, I can point to another paper of my research group in which we analyze the efficiency of the 3-majority protocol: each node makes a random sample of three other nodes, observes their opinion and then updates its own one to the majority of them. Again, our analysis is valid on the complete graph; extending this result to mobile networks is a challenging open question.
