List of Internship Subjects

• Belief Propagation in Complex Networks
• The effect of graph structure on Network Coding performance

Belief Propagation in Complex Networks
Supervisors: Giovanni Neglia and Konstantin Avrachenkov
Team: Maestro
Place: INRIA Sophia Antipolis Méditerranée, 2004 route des Lucioles, Sohia Antipolis, France
Description:
Network science [1] has emerged in the last ten years as an inter-disciplinary and yet distinct research field, seeking to discover common principles, algorithms and tools that govern networks as different as the Internet, the web, human social networks, gene regulatory networks, the brain, ecosystems, social organizations, transport networks. The pioneer work from applied mathematicians and statistical physicists, like Strogatz, Watts, Barabasi and Vespignani, has focused on (1) identifying common properties of these networks (small diameter, high clustering coefficients, presence of hubs, etc.), (2) proposing simple network growth models (e.g.~random links, preferential attachment) that may justify such commonalities across scenarios so heterogeneous, and (3) studying the consequence of these properties on performance like propagation speed in the network (of rumors, diseases, data packets), or robustness to attacks. More recently, researchers have also started studying the interplay of different networks, to lead to predictive models of the individual and composite behavior of these complex interacting networks. For example, a significant funding from the U.S. Department of Defense has lead in 2009 to the creation of 3 academic research centers (respectively on information, social-cognitive and communication networks) and one interdisciplinary research center. An important issue, common to different networks, is how beliefs form: it concerns political opinion in voting, product quality as perceived by customers, intentions in potential conflict situations, but also optimization of distributed algorithms in wireless networks. Beliefs form and evolve over time on the basis of private information, but also of information exchange with "neighbours" in the specific network (neighbours may be friends, bloggers, other customers shopping or mobile devices having an opportunity to transmit each other). As a starting point, we consider the case where the graph of the network of interactions is given and the agents can communicate only with their direct neighbors on the graph. A central question is how network characteristics---like the topology of the communication network and the type of information exchangeable among the agents---affect belief formation dynamics. For example, under what conditions do these dynamics lead to an efficient aggregation of the information disperse among all the agents, and then to the emergence of a common correct belief in the whole network? Our first results in this direction are in [2], where the agents are mobile wireless nodes in a Delay Tolerant Network, that try to collectively optimize a parameter of their routing algorithm. In this case the belief of each node is its current estimate of the optimal value of such parameter. We considered that the communication network evolves over time due to nodes mobility: a link is created (/destroyed) every time two nodes move inside (/outside) the transmission range of each other. The dynamic evolution of the topology is assumed to follow a Markovian process. As regards the learning algorithm, nodes update their belief by simply averaging it with their neighbors similarly to what is done in consensus algorithms. We show that this learning algorithm together with a distributed form of gradient descent is sufficient to guarantee the convergence to the optimal value of the parameter (i.e. the correct belief).
In this framework, the student would study the speed of convergence of consensus algorithms and in particular how it depends on the network structure and on the choice of the weigths used in the average. In fact, an opportune choice of the weights could speed up the convergence for a given meeting process: intuitively more weight should be given to the hubs of the communication network, e.g. to the nodes that meet more often other nodes or that travel between otherwise disconnected regions. The student will overview the existing literature on convergence speed of consensus algorithms (e.g. [3] and [4]), and perform a simulation analysis of consensus algorithms on different graphs.
[1] An introductory video to Network Science
[2] Distributed Sub-gradient Method for Delay Tolerant Networks, R. Masiero, G. Neglia, INRIA Research Report 7345, August 2010, [pdf]
[3] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Trans. Inf. Theory, vol. 52, pp. 2508–2530, Jun. 2006, [pdf]
[4] Jakovetić, D.; Xavier, J.; Moura, J.M.F.; , "Weight Optimization for Consensus Algorithms With Correlated Switching Topology," Signal Processing, IEEE Transactions on , vol.58, no.7, pp.3788-3801, July 2010 doi: 10.1109/TSP.2010.2046635, [pdf]

The effect of graph structure on Network Coding performance
Supervisors: Giovanni Neglia and Lucile Sassatelli
Team: Maestro,SigNet
Place: INRIA Sophia Antipolis Méditerranée, 2004 route des Lucioles, Sohia Antipolis, France
Description:
In network coding, the coding is not performed at the information source, but rather by the relay nodes in the network, that can combine several packets together for transmission. For example, Random Linear Coding (RLC) is a form of network coding, where nodes forwards random linear combinations of the data they receive. This can be used to attain the maximum possible information flow in a network (the classic example of a butterfly network can be found on wikipedia [2]). First introduced in [3] for multicast, RLC has later been applied to networked scenarios including P2P content distribution [4], gossip protocol [5], distributed storage [6], broadcast [7,8] and unicast [9] in mobile or static wireless networks (including Delay Tolerant Networks. The purpose of the project is to study the performance of network coding under different graph models (Watt-Strogatz, Barabasi, etc.), both static and dynamic (e.g. links are intermittently active/inactive). It would be interesting to understand how the characteristics of the graph (like diameter, clustering, degree distribution) affect information diffusion when network coding is used. This study could provide important insights for the use of network coding in mobile social networks
The student will overview the existing literature, and then perform a simulation analysis of network coding on the different graphs.
[1] Ahlswede, Rudolf; N. Cai, Shuo-Yen Robert Li, and Raymond Wai-Ho Yeung, Network Information Flow. IEEE Transactions on Information Theory, IT-46 46: 1204–1216. 2000.
[2] Network Coding on Wikipedia
[3] T. Ho, R. Hoetter, M. Médard, D. R. Karger, and M. Effros. The benefits of coidng over routing in a randomized setting. In IEEE International Symposium on Information Theory, 2003.
[4] C. Gkantsidis and P. Rodriguez. Network coding for large scale content distribution. Infocom, 2005.
[5] S. Deb and M. Médard. Algebraic gossip: A network coding approach to optimal multiple rumor mongering. 2004. Proc. Allerton.
[6] S. Acedanski, S. Deb, M. Médard, and R. Koetter. How good is random linear coding based distributed networked storage. In Netcod, 2005.
[7] J. Widmer and J.-Y. Le Boudec. Network coding for efficient communication in extreme networks. WDTN, 2005.
[8] J. Widmer, C. Fragouli, and J.-Y. Le Boudec. Energy-efficient broadcasting in wireless ad-hoc networks. In Netcod 2005.
[9] X. Zhang, G. Neglia, J. Kurose, D. Towskey, On the Benefits of Random Linear Coding for Unicast Applications in Disruption Tolerant Networks. In Netcod 2006.