Grant: Engage Grants Program
University of Ottawa
$25,000.00
Developing advanced techniques for sampling online social networks
FY 2012-13
Summary
Analyzing or Mining Online Social Networks (OSN) has become one of the most pressing problems of
modern-day data mining. This is due to the exponential growth of these networks which are becoming
increasingly popular (e.g., Facebook, Twitter, Linkedln and cellular networks) and which include more and
more information that can be useful for commercial purposes, management issues, and even for defense and
security applications.
The reason why research on Social Network Analysis to date has been limited is that the size of online
networks is overwhelming. No analytic tool can process anything close to this amount of data. The only way
that any kind of analysis can be made possible is by sampling from the huge network and working on this
sample. Standard sampling techniques such as breadth-first search and random walks have been used, but it has
been shown that such techniques yield a bias toward the most highly connected nodes. Of course, this is
unacceptable since, in order for the analysis to be of any use, the sampling must be uniform over the entire
population. It has recently been shown that Monte Carlo Markov Chain (MCMC) methods can create unbiased
samples suitable for the problem of Social Network Analysis. However, MCMC techniques come with
significant challenges: significant burn-in lengths and correlation with the initial node choice.
The purpose of our proposed research is to develop a new approach and a theoretical foundation for sampling
OSNs that will address these issue. We are proposing to use the following three ideas or techniques:
1) An adaptive technique from MCMC called Coupling from the Past;
2) Reductions of the computational burden though the parallelization of the MCMC process.
3) A theoretical framework for the new approach based on the idea of Order Statistics.
Program
Engage Grants Program
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
431154-2012
Name nom
Japkowicz, Nathalie
Department département
Electrical Engineering and Computer Science , School of
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
25000
Program id
EGP
Program name en
Engage Grants Program
Program name fr
Programme de subventions d'engagement partenariat
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
1553
Committee name en
Ontario Internal Decision Committee
Committee name fr
Comité de décision interne pour l'Ontario
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Partie
1
Nb partie
1
Application title
Developing advanced techniques for sampling online social networks
Keyword
NSERC
Application summary
Analyzing or Mining Online Social Networks (OSN) has become one of the most pressing problems of
modern-day data mining. This is due to the exponential growth of these networks which are becoming
increasingly popular (e.g., Facebook, Twitter, Linkedln and cellular networks) and which include more and
more information that can be useful for commercial purposes, management issues, and even for defense and
security applications.
The reason why research on Social Network Analysis to date has been limited is that the size of online
networks is overwhelming. No analytic tool can process anything close to this amount of data. The only way
that any kind of analysis can be made possible is by sampling from the huge network and working on this
sample. Standard sampling techniques such as breadth-first search and random walks have been used, but it has
been shown that such techniques yield a bias toward the most highly connected nodes. Of course, this is
unacceptable since, in order for the analysis to be of any use, the sampling must be uniform over the entire
population. It has recently been shown that Monte Carlo Markov Chain (MCMC) methods can create unbiased
samples suitable for the problem of Social Network Analysis. However, MCMC techniques come with
significant challenges: significant burn-in lengths and correlation with the initial node choice.
The purpose of our proposed research is to develop a new approach and a theoretical foundation for sampling
OSNs that will address these issue. We are proposing to use the following three ideas or techniques:
1) An adaptive technique from MCMC called Coupling from the Past;
2) Reductions of the computational burden though the parallelization of the MCMC process.
3) A theoretical framework for the new approach based on the idea of Order Statistics.