Completed Projects

PhD candidate New tools and Algorithms for Directed NEtwork Analysis (NADINE)

 

The NADINE project, which is funded by the EU Seventh Framework Programme, is a collaborative effort of the Centre National de la Recherche Scientifique (CNRS), France; University of Twente, The Netherlands; Magyar Tudomanyos Akademia Szamitastechnikai es Automatizalasi Kutato Intezet, Hungary; Universita degli Studi di Milano, Italy. The current PhD project is a part of NADINE, and will be conducted in SOR (Stochastic Operations Research) chair within the faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) at the University of Twente (UT; http://www.utwente.nl), which is an entrepreneurial research university, located in Enschede, the Netherlands. Most of the faculty's research, including the present project, is part of the multidisciplinary research institute Centre for Telematics and Information Technology (http://www.ctit.utwente.nl).


The challenge

NADINE aims at developing new algorithms to facilitate classification and information retrieval from large directed networks. The Google matrix formed by the links of the network will be analyzed by analytical tools of Stochastic Processes, Random Matrix Theory and quantum chaos and by efficient numerical methods for large matrix diagonalization including the Arnoldi method. New tools and algorithms produced by the project will create fundamental basis for development of new types of tools and algorithms for modern networks, including mobile communication networks which will play more and more important role in future. New characterization of complex networks will allow to manage in an efficient and rapid way information extraction for social networks, communication and other networks. The project will create efficient voting systems in social networks that will pave the way for new types of democracy solutions in societies at a high communication level.

The PhD project at the University of Twente, in collaboration with partners, will lay mathematical foundations for development and application of new ranking schemes, such as 2DRanking, and provide fast algorithms for their computation.

The research line within NADINE, in which the PhD student will contribute, consists of the following tasks.
First, we use novel statistical methods for measuring dependencies in directed networks, and formally interpret and provide techniques for reproducing the observed correlations in random directed graphs. Many networks share the famous scale-free property, expressed in power law degree distributions. However, correlations between network parameters are often network-specific. For example, the correlations between the PageRank and the in-degree of a node are strikingly different in e.g. Web and Wikipedia.
Next goal is to carry out a probabilistic analysis and derive the probability distribution for the 2DRanking. This will be done by using local approximation of a network by a branching tree. The novelty and challenge will be to model the 2DRanking and include the graph correlations in the model. The obtained analytical results will reveal the influence of the network parameters and network correlations on the centrality measures. This will provide sufficient grounds for designing new, model-based and network-specific centrality measures that take advantage of network structure in an optimal way. Effects of dynamical link variations in time and their influence on the ranking schemes will be analysed.
Finally, our objective is to develop efficient Monte Carlo algorithms for evaluating centrality measures. Such methods are remarkably efficient if the goal is to evaluate the ranking order, and not the exact values of centrality scores. Our aim is to evaluate the required computational complexity of Monte Carlo algorithms in order to produce an informative ranking order.


Our offer

We offer a contract for four years. The extent of this position is a maximum of 38 hours per week according to the Dutch university rules.
The monthly salary of a PhD student, in accordance with the Dutch universities collective labour agreement, ranges from €2042 gross in the first year to €2612 gross in the fourth year. In addition to this we offer a holiday allowance (amounts to 8%) and an end-of-year bonus (amounts to 8.3%) and a number of additional benefits. Furthermore, the University of Twente provides excellent facilities for professional and personal development.


Your profile

You have completed a university degree (MSc level) or are about to graduate, in (applied) mathematics or a closely related field. You have intellectual curiosity and knowledge of probability theory, stochastic processes, and/or design of numerical algorithms. Strong skills in programming and analysis of large data sets are highly desirable for this project. Your main responsibility will be to carry out research, but you will be given the opportunity to acquire some teaching experience.

Information
More information can be obtained from dr. Nelly Litvak (n.litvak@utwente.nl).

Application
Candidates are invited to send their application together with curriculum vitae, marks transcripts, and the names and addresses of two referees by using the application link. Applications should be received before 1st July, 2012.


The Organisation

The University of Twente. We stand for life sciences and technology. High tech and human touch. Education and research that matter. New technology which drives change, innovation and progress in society. The University of Twente is the only campus university in the Netherlands; divided over six faculties we provide more than fifty educational programmes. The University of Twente has a strong focus on personal development and talented researchers are given scope for carrying out pioneering research.



The faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) comprises three disciplines that shape Information and Communication Technology. ICT is more than communication. In almost every product we use mathematics, electronics and computer technology and ICT now contributes to all of societies' activities. The faculty works together intensively with industrial partners and researchers in the Netherlands and abroad and conducts extensive research for external commissioning parties and funders. The research which enjoys a high profile both at home and internationally, has been accommodated in the multidisciplinary research institutes MESA+, CTIT and MIRA.

 

Apply here