Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Windsor

$32,000.00

Mining Online Social Networks and Hidden Web Data Sources by Sampling

FY 2016-17

Summary
Searchable web interfaces in the form of HTML search boxes, programmable web APIs and Web Services are ubiquitous on the web. The data hidden behind search interfaces are collectively called the hidden web or deep web. It can be virtually everything on the web when the search box is the interface to a web search engine such as Google. In other cases, the deep web data can be valuable collections of data in a specialized area, such as an Online Social Network (OSN) site. From these vast and ever increasing data sources that are openly accessible, a question of interests to both data providers and consumers is: what information and patterns can be inferred statistically from a sample. The answer to this question has many applications ranging from business intelligence to criminal group detection. Although our main goal is to uncover the hidden properties, the same techniques can be used by data providers to design the searchable interfaces to protect the data. Our short-term goal focuses on mining OSNs, and the long-term goal is to study the theories and methods that are applicable to other deep web data sources and large local data collections. New challenges arise in mining OSNs, because the data, the way to access the data, and the properties and patterns to be inferred from the data, are different from that of conventional data mining problems. First, the data in its entirety is not available. Instead, only a small portion of the data can be returned by invoking costly remote calls through web APIs. We need to develop sampling methods tailored for the web interfaces. Second, the data sources are huge, often following the power-law distribution with very large variance. This calls for new sampling methods to reduce the variance. Third, some properties to be estimated and patterns to be discovered are beyond the scope of traditional data mining tasks. Social network properties such as the clustering coefficient and various centralities are costly to compute even when we possess the whole data. To overcome these difficulties, we target the following goals: (1) To obtain random samples using web interfaces. Inferencing directly on uncontrolled data returned by web interfaces will result in substantial and unpredictable bias. Web interfaces are restrictive, and vary in the types of the queries they accept, the way they index the content, and the strategy they rank and return the matches. The remote queries are expensive because of network traffic and daily quota imposed by data providers. Our goal is to, by using limited number of queries, maximize the amount of sample data that are useful to infer OSN properties. (2) To design graph sampling methods to reduce variance: Samples are useful when they are selected from certain distributions. Conventional wisdom has it that uniform random samples should be used whenever possible. However, OSNs are large and scale-free, resulting in large variances for many estimators on uniform random samples. Our goal is, in the context of graph sampling that is independent of the web interface, to develop other sampling methods that can increase the accuracy of the inferences. (3) To infer OSN properties: In addition to summarizing statistics, we will develop sampling and estimation methods for metrics in social network studies. Based on these explorations, we will adapt and combine these methods to real OSNs such as Twitter, Facebook , LinkedIn and Weibo to discover their interesting social network properties, phenomena that are unique in OSNs (e.g., robot accounts), and other unsuspected patterns of wide interests.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-04463
Name nom
Lu, Jianguo
Department département
Computer Science, School of
Organization id
37
Institution établissement
University of Windsor
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
32000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2710
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information systems design
Research subject fr
Conception de systèmes d'information
Partie
3
Nb partie
5
Application title
Mining Online Social Networks and Hidden Web Data Sources by Sampling
Keyword
NSERC
Application summary
Searchable web interfaces in the form of HTML search boxes, programmable web APIs and Web Services are ubiquitous on the web. The data hidden behind search interfaces are collectively called the hidden web or deep web. It can be virtually everything on the web when the search box is the interface to a web search engine such as Google. In other cases, the deep web data can be valuable collections of data in a specialized area, such as an Online Social Network (OSN) site. From these vast and ever increasing data sources that are openly accessible, a question of interests to both data providers and consumers is: what information and patterns can be inferred statistically from a sample. The answer to this question has many applications ranging from business intelligence to criminal group detection. Although our main goal is to uncover the hidden properties, the same techniques can be used by data providers to design the searchable interfaces to protect the data. Our short-term goal focuses on mining OSNs, and the long-term goal is to study the theories and methods that are applicable to other deep web data sources and large local data collections. New challenges arise in mining OSNs, because the data, the way to access the data, and the properties and patterns to be inferred from the data, are different from that of conventional data mining problems. First, the data in its entirety is not available. Instead, only a small portion of the data can be returned by invoking costly remote calls through web APIs. We need to develop sampling methods tailored for the web interfaces. Second, the data sources are huge, often following the power-law distribution with very large variance. This calls for new sampling methods to reduce the variance. Third, some properties to be estimated and patterns to be discovered are beyond the scope of traditional data mining tasks. Social network properties such as the clustering coefficient and various centralities are costly to compute even when we possess the whole data. To overcome these difficulties, we target the following goals: (1) To obtain random samples using web interfaces. Inferencing directly on uncontrolled data returned by web interfaces will result in substantial and unpredictable bias. Web interfaces are restrictive, and vary in the types of the queries they accept, the way they index the content, and the strategy they rank and return the matches. The remote queries are expensive because of network traffic and daily quota imposed by data providers. Our goal is to, by using limited number of queries, maximize the amount of sample data that are useful to infer OSN properties. (2) To design graph sampling methods to reduce variance: Samples are useful when they are selected from certain distributions. Conventional wisdom has it that uniform random samples should be used whenever possible. However, OSNs are large and scale-free, resulting in large variances for many estimators on uniform random samples. Our goal is, in the context of graph sampling that is independent of the web interface, to develop other sampling methods that can increase the accuracy of the inferences. (3) To infer OSN properties: In addition to summarizing statistics, we will develop sampling and estimation methods for metrics in social network studies. Based on these explorations, we will adapt and combine these methods to real OSNs such as Twitter, Facebook , LinkedIn and Weibo to discover their interesting social network properties, phenomena that are unique in OSNs (e.g., robot accounts), and other unsuspected patterns of wide interests.