III: Small: Discovering and Characterizing Implicit Links in Graph Data

图数据代表了各种各样的现象，从交通数据、生物网络到社会网络。社交网络使人们能够参与各种在线活动。一个典型的社交网站允许用户明确地为其他用户指定带有“标签”的“积极”链接，例如家庭、友谊、Twitter追随者等。很少关注“隐性链接”，即社交用户之间可能表明竞争、不信任、不喜欢或对抗的未指定链接。本项目研究理解和识别图数据中隐含链接的基本数据分析问题。该项目探索新的计算技术，以发现大规模图形数据（如社交网络）中可操作和有洞察力的模式，并使计算社会科学中对社交媒体用户行为的大规模研究成为可能。通过该项目获得的研究见解有望在具有正链接和隐链接的网络上更好地设计有监督和无监督学习算法。对隐式社交网络链接的研究将适用于新的推荐系统的设计，从而改善服务和用户体验。建议的研究将涉及研究生和本科生进行他们的论文或项目。研究课题和成果将整合到本科和研究生教育中。提出的研究解决了大规模、不完整和嘈杂网络（如底层社交媒体）中的链接分析问题。由于用户之间的隐性链接在社交网站上通常是不可见的，发现它们需要新的挑战。研究小组建议评估隐性链接对关系发现和更好的社会网络理解的价值。该项目包括图形数据分析算法的开发，异构跨媒体数据中积极和未标记链接发现的机器学习，以及计算效率高的隐式链接预测。该团队建议将研究见解应用于改进推荐系统设计，隐式用户关系分类和社交用户聚类。研究小组计划通过该项目网站（http://www.public.asu.edu/~huanliu/projects/ImplicitLinks/），与研究界分享包括基准数据在内的该项目成果，以促进社交网络中隐式链接发现的研究。

Graph data represent a variety of phenomena, ranging from traffic data, biological networks to social networks. Social networks enable people to participate in a variety of online activities. A typical social networking site allows users to explicitly specify "positive" links to other users with "labels" such as family, friendships, Twitter follower, etc. Little attention is paid to "implicit links" which are unspecified links among social users that may indicate competition, distrust, dislike, or antagonism. This project studies fundamental data analytics issues of understanding and identifying implicit links in graph data. The project explores new computational techniques to discover actionable and insightful patterns in large-scale graph data (e.g., social networks) and enables a large-scale study of social media user behaviors in computational social science. The research insights gained through this project are expected to lead to better design of supervised and unsupervised learning algorithms on networks with both positive and implicit links. The study of implicit social network links will be applicable to the design of new recommender systems, leading to improved services and user experience. The proposed research will involve graduate and undergraduate students in pursuing their theses or projects. Research topics and findings will be integrated in undergraduate and graduate education. The proposed research addresses issues of link analysis in large-scale, incomplete, and noisy networks, such as underlying social media. As implicit links between users are typically invisible on social networking sites, discovering them entails novel challenges. The research team proposes to evaluate the value of implicit links for relationship discovery and better social network understanding. The project includes development of algorithms for graph data analytics, machine learning for positive and unlabeled link discovery in heterogeneous cross-media data, and computationally efficient implicit link predictions. The team proposes to apply the research insights to improving recommendation systems design, classification of implicit user relationships, and social user clustering. The research team plans to share results of this project, including benchmark data with the research community to promote the research on implicit link discovery in social networks via the project site (http://www.public.asu.edu/~huanliu/projects/ImplicitLinks/).