Mining Online Social Networks and Hidden Web Data Sources by Sampling

HTML搜索框、可编程Web API和Web服务形式的可搜索Web界面在Web上无处不在。隐藏在搜索界面后面的数据统称为隐藏网络或深网。 当搜索框是网络搜索引擎（如Google）的界面时，它几乎可以是网络上的一切。 在其他情况下，深网数据可以是专门领域（诸如在线社交网络（OSN）站点）中的有价值的数据集合。 从这些可公开访问的庞大且不断增加的数据源中，数据提供者和消费者都感兴趣的一个问题是：可以从样本中统计推断出哪些信息和模式。这个问题的答案有许多应用，从商业智能到犯罪集团侦查。虽然我们的主要目标是发现隐藏的属性，但数据提供者可以使用相同的技术来设计可搜索的接口以保护数据。 我们的短期目标是挖掘OSN，长期目标是研究适用于其他深网数据源和大型本地数据集的理论和方法。 OSN挖掘面临着新的挑战，因为数据、访问数据的方式以及从数据中推断出的属性和模式与传统的数据挖掘问题不同。首先，没有完整的数据。相反，只有一小部分数据可以通过Web API调用昂贵的远程调用来返回。 我们需要开发为Web界面量身定制的采样方法。第二，数据源庞大，通常遵循具有非常大方差的幂律分布。这就需要新的抽样方法来减少方差。 第三，要估计的一些属性和要发现的模式超出了传统数据挖掘任务的范围。 即使我们拥有全部数据，计算诸如聚类系数和各种中心性之类的社交网络属性也是昂贵的。 为了克服这些困难，我们有以下目标： (1)使用Web界面获取随机样本。 直接对Web接口返回的不受控制的数据进行推理将导致大量和不可预测的偏差。 Web接口是有限制的，并且在它们接受的查询类型、它们索引内容的方式以及它们排名和返回匹配的策略方面有所不同。 由于网络流量和数据提供商强加的每日配额，远程查询是昂贵的。我们的目标是，通过使用有限数量的查询，最大限度地提高样本数据的数量是有用的推断OSN属性。 (2)设计图形抽样方法以减少方差：当从某些分布中选择样本时，样本非常有用。传统观点认为，应尽可能使用统一的随机样本。然而，OSN是大的和无标度的，导致在均匀随机样本的许多估计大的方差。我们的目标是，在独立于Web界面的图形采样的背景下，开发其他可以提高推断准确性的采样方法。 (3)要推断OSN属性，请执行以下操作：除了总结统计数据外，我们还将开发社交网络研究中指标的抽样和估计方法。 在这些探索的基础上，我们将把这些方法改编并联合收割机结合到真实的OSN中，如Twitter、Facebook、LinkedIn和微博，以发现它们有趣的社交网络属性、OSN中特有的现象（例如，机器人账户），以及其他未被怀疑的广泛兴趣模式。

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.