Reliability Queries and Influence Maximization in Uncertain Networks

Thursday, June 27, 2019

2.30 p.m.

ISI seminar room 1st floor

Prof. Arijit Khan School of Computer Science and Engineering Nanyang Technological University, Singapore

Uncertainty is evident in graph data due to a variety of reasons, such as noisy measurements, inconsistent, incorrect, and possibly ambiguous information sources, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. In these cases, data is represented as an uncertain network: A graph whose nodes, edges, and attributes are accompanied with a probability of existence. With the popularity of uncertain data, uncertain graphs are increasingly becoming important in many emerging application domains including biological networks, knowledge bases, social networks, viral marketing, road networks, crowd‐sourcing, among many others. While many classical graph algorithms such as reachability and shortest path queries become #P‐complete, and hence, more expensive in uncertain graphs, various complex queries are also emerging over uncertain networks, such as influence maximization as a service provided by the social network host.
In the first half of the talk, I shall discuss our recent empirical analysis by comparing six state‐of‐the‐art uncertain graph reliability estimation methods, our recommendations about them, and how to further improve their performance, as well as our algorithmic development in improving the network reliability by adding a limited number of new edges. In the second half of the talk, I shall introduce our works on novel influence maximization queries, such as improving a social network host’s revenue that sells viral marketing campaigns to multiple client campaigners, how to identify the top‐r product features that maximize the spread of influence from the seed users to a set of target customers, as well as how to maximize contrasting opinions in a signed, social network. I shall conclude by emphasizing the current challenges and highlighting some future research directions.

Arijit Khan is an assistant professor (tenure‐track) in the School of Computer Science and Engineering, Nanyang Technological University, Singapore. He earned his PhD from the Department of Computer Science, University of California, Santa Barbara, USA, and did a post‐doc in the Systems group at ETH Zurich, Switzerland. Arijit is the recipient of the prestigious IBM PhD Fellowship in 2012‐13. He published more than 35 papers in premier databases and data mining conferences and journals including ACM SIGMOD, VLDB, IEEE TKDE, IEEE ICDE, SIAM SDM, USENIX ATC, EDBT, and ACM CIKM. Arijit co‐presented tutorials on emerging graph queries and big graph systems at IEEE ICDE 2012, and at VLDB (2017, 2015, and 2014). He served in the program committee of ACM KDD, ACM SIGMOD, VLDB, IEEE ICDE, IEEE ICDM, EDBT, ACM CIKM, and in the senior program committee of WWW. Arijit served as the co‐chair of Big‐O (Q) workshop co‐located with VLDB 2015, wrote a book on uncertain graphs in Morgan & Claypool’s Synthesis Lectures on Data Management. He contributed invited chapters and articles on big graphs querying and mining in the ACM SIGMOD blog, Springer Handbook of Big Data Technologies, and in Springer Encyclopedia of Big Data Technologies. He was invited to give tutorials and talks across 10 countries, including in the National Institute of Informatics (NII) Shonan Meeting on "Graph Database Systems: Bridging Theory, Practice, and Engineering", 2018, Japan, Asia Pacific Web and Web‐Age Information Management Joint Conference on Web and Big Data (APWeb‐WAIM 2017), International Conference on Management of Data (COMAD 2016), and in the Dagstuhl Seminar on “Systems and Algorithms for Large‐scale Graph Analytics”, 2014 , Schloss Dagstuhl ‐ Leibniz Center for Informatics, Germany.