Online social networks have been widely studied. In this talk, we discuss some interesting research issues related to online social networks including structural diversity search, influential community, strong/weak ties, and social hierarchy. For the structural diversity search, we discuss the observation that in a social contagion process the probability of contagion is tightly controlled by the number of connected components in an individual's neighborhood, and discuss the way to find top-k users in a social network with the highest structural diversity. For the influential community, we discuss a new way to find a group of users that have high influence. For the strong/weak ties, we discuss it related to the triangles, where the number of triangles is a fundamental metric for analyzing the structure and function of a network. Finally, we discuss social hierarchy, since social hierarchy (i.e., pyramid structure of societies) is a fundamental concept in sociology and social network analysis. The importance of social hierarchy in a social network is that the topological structure of the social hierarchy is essential in both shaping the nature of social interactions between individuals and unfolding the structure of the social networks. The social hierarchy found in a social network can be utilized to improve the accuracy of link prediction, provide better query results, rank web pages, and study information flow and spread in complex networks. We model a social network as a directed graph G, and the social hierarchy is as DAG (directed acyclic graph) of G. By DAG, all the vertices in G can be partitioned into different levels, the vertices at the same level represent a disjoint group in the social hierarchy, and all the edges in DAG follow one direction. We discuss the properties of GD found, the applications, and the algorithms.

Jeffrey Xu Yu received his B.E., M.E. and Ph.D. in Computer Science, from the University of Tsukuba, Japan, in 1985, 1987 and 1990, respectively. Dr. Yu held teaching positions in the Institute of Information Sciences and Electronics, University of Tsukuba, Japan, and the Department of Computer Science, The Australian National University. Currently, he is a Professor in the Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong. His current main research interests include graph mining, graph query processing, graph pattern matching, keywords search in databases, and online social networks. Dr. Yu served as an Information Director and a member in ACM SIGMOD executive committee (2007-2011), an associate editor of IEEE Transactions on Knowledge and Data Engineering (2004-2008), and an associate editor in VLDB Journal (2007-2013). Currently he servers as an associate editor of WWW Journal, the International Journal of Cooperative Information Systems, the Journal on Health Information Science and Systems (HISS), and Journal of Information Processing. Dr. Yu served/serves in many organization committees and program committees in international conferences/workshops including PC Co-chair of APWeb'04, WAIM'06, APWeb/WAIM'07, WISE'09, PAKDD'10, DASFAA'11, ICDM'12, NDBC'13, ADMA'14, and CIKM'15.

新しいスーパーコンピュータの応用として大規模なグラフ解析が注目を集めている. グラフ解析の応用分野としては大規模災害等での避難誘導計画，社会公共政策や企業経営等のためソーシャル・ネットワーク等の大規模データの有効活用等が想定されているが, 非常に計算量やデータ量さらに電力使用量などの規模が大きく従来の手法では処理が困難である. そのためハイパフォーマンスコンピューティング分野の技術を用いて大規模なグラフ解析を行う研究がさかんに行われており,高速かつ省電力なグラフ解析ソフトウェアの開発方法について解説を行う. 現在、都市 OS 開発などのサイバーフィジカルシステムにおいて、ヒト・モノのモビリティに関する数理モデル及び最適化手法としてのグラフ解析の利用が開始されている。このような最先端理論（Algorithm Theory）+ 大規模実データ（Big Data）+ 最新計算技術（Computation）の有機的な組合せによる最新のグラフ解析の応用について紹介を行う．

1993年早稲田大学理工学部卒業．1998年東京工業大学大学情報理工学研究科博士課程修了:博士(理学)．現在 九州大学マス・フォア・インダストリ研究所教授及びJST CREST ポストペタスケールシステムにおける超大規模グラフ最適化基盤：研究代表者。2013年日本オペレーションズ・リサーチ学会研究賞。2014年〜2015年第8, 10, 11回 Graph500 ベンチマークコンテスト世界１位受賞．2013年〜2015年第１回〜6回 Green Graph500 ベンチマークコンテスト世界１位受賞．