Data Credibility, Diversity and Privacy in Large Graph Analytics

我们今天面临的最大挑战之一是需要处理大量的信息。迫切需要分析大量、高度相互关联和不断发展的数据，目的是获取知识，帮助我们在业务增长、公共管理、卫生、国防和环境等应用领域做出重要决策。图是表示高度互连数据的自然选择。本研究计划解决了三个核心领域的挑战，即大图形分析、数据可信度、多样性和隐私。我们研究的第一个主题是社交网络的可信图形分析。在线社交网络是一种有效的媒介，可以在短时间内将信息传播给数百万人。虽然通过网络传播信息的便利性可能是有益的，但如此大规模的错误信息传播可能会引起恐慌并产生破坏性影响。为了保证接收到的信息的可信度，设计算法来检测和限制错误信息的传播是很重要的。我们在数据可信度方面的工作将设计可扩展的算法来打击错误信息的传播。我们研究的第二个主题是基于多样性的图形分析，用于产品推荐和社会影响。推荐系统中的许多问题（将项目分配给用户）可以建模为图匹配问题。然而，这些问题太弱，无法对推荐列表的多样性进行建模，而推荐列表是衡量用户满意度的重要指标。我们在数据多样性方面的工作将考虑推广已知图匹配模型的新方法，以满足多样性需求。我们将研究如何在社交网络中捕捉多样性，目标是在这些网络中发现更有影响力的社区。我们探索的第三个主题是隐私感知图形分析。虽然挖掘电子健康记录等数据的需求已得到广泛认可，但确保在发布数据之前满足隐私需求非常重要。匿名化方法通过最小程度地干扰数据来实现隐私，而差分隐私仅通过噪声添加发布统计摘要来同时保证有用性和隐私性。我们在数据隐私方面的工作将使用统计理论和实践中的有效方法，即copulas，解决与匿名化方法和差分隐私相关的重要开放问题。这一创新研究项目将带来三方面的好处：(1)我们证明的结果将有助于形成这些主题的高质量学术知识体系。(2)培训HQP以适应对技能要求较高的岗位。(3)我们在这个研究项目中开发的快速、可扩展的算法将弥合理论与实践之间的差距，并将与加拿大企业和其他公共和私营部门的组织高度相关。

One of the biggest challenges we face today is the need to handle large amounts of information. There is an urgent need to analyze data which is massive, highly interconnected and evolving with the goal of obtaining knowledge that aids us in making important decisions in application domains such as business growth, public administration, health, defense and the environment. Graphs are a natural choice to represent highly interconnected data. This research proposal addresses challenges in three core areas of large graph analytics, data credibility, diversity, and privacy.The first topic we study is credible graph-analytics for social networks. Online social networks are efficient as a medium to spread information to millions of people in a short amount of time. Although the ease of information propagation through the network can be beneficial, spread of misinformation at such large scale can cause panic and have a disruptive effect. In order to ensure the credibility of the information received, it is important to design algorithms to detect, and limit the spread of misinformation. Our work in data credibility will design scalable algorithms for combating spread of misinformation. The second topic we investigate is diversity-based graph-analytics for product recommendation and social influence. Many problems in recommender systems, that assign items to users, can be modeled as graph matching problems. However, these problems are too weak to model diversity in recommendation lists, an important metric aimed at user satisfaction. Our work in data diversity will consider new ways to generalize known graph matching models in order to address diversity needs. We will investigate how to capture diversity in social networks, with the goal of discovering more influential communities in those networks.The third topic we explore is privacy-aware graph-analytics. While the need for mining data such as e-health records has been widely recognized, ensuring that privacy needs are met before releasing the data is important. Anonymization methods achieve privacy by perturbing the data minimally while differential privacy only publishes a statistical summary using noise addition to ensure usefulness and privacy simultaneously. Our work in data privacy will tackle important open problems related to anonymization methods and differential privacy using effective methods from statistical theory and practice, namely, copulas.The benefit of this innovative research program will be three-fold: (1) The results we prove will contribute to the body of top quality academic knowledge on each of these topics. (2) It will train HQP for positions that require highly desired skills. (3) The fast, scalable algorithms we develop in this research program will bridge the gap between theory and practice and will be highly relevant to Canadian businesses and other organizations in the public and private sector.