Social networks explicitly exhibit relations (called ties in social sciences) among individuals and groups (called actors). They have been studied in social sciences since the 1930s to analyze social phenomena. Interaction patterns reveal relations among actors (such as persons, groups, companies), which can be merged to produce valuable information as a network structure. The power of social network analyses has become apparent through its use for orienting ideas and specific bodies of methods. Many applications are relevant to social networks: trust realization, ontology construction, community discovering, knowledge sharing, etc. While shaping our own knowledge, social networks are a strong influence shaping our lives.

Originally in social sciences, social networks are extracted through observations and interviews. The typical approach of questionnaire surveys is often used to obtain social networks, e.g., asking "please indicate which persons you would regard as your friend." Recent technologies have enabled us to obtain social network data from e-mail archives, electronic libraries, schedule data, and Web citation information. By virtue of the current trends of "Web 2.0", "Semantic Web", and "Web 3.0", a huge amount of information has become available on the Web. Current Web applications such as Wikis and blogs enable users to create and publicize their contents on the Web easily. Moreover, social networking services (SNSs) provide a foundation for users to communicate with their friends on the Web space. As an entrance to the Web corpus, a search engine is useful to access various information that is available on the Web. Extracting and analyzing social networks from the Web is expected to yield timely, comprehensive information of the real world on the Web.

Overall, in this thesis, we address two research topics for social networks on the Web:

(1) How to extract various social networks from the Web, and

(2) How to use and apply social networks mined from the Web.

Regarding the first topic, several methods exist to extract social networks including people (particularly researchers) from the Web using a search engine. In this thesis, we describe expansion of existing techniques to obtain social networks among various entities on the Web so that they become applicable to various domains. We propose two improvements-relation identification and threshold tuning-which enable us to address complex and inhomogeneous communities. For the first improvement of relation identification for the complex communities, we extract social networks among companies as examples. Extraction of relations between a pair of companies is realized using a search engine and text processing. Because names of companies co-appear coincidentally on the Web, we propose an advanced algorithm, which is characterized by the addition of keywords (relation keywords) to a query. The relation keywords are obtained from the Web using a Jaccard coefficient. This method is a first attempt to extract companies' social networks from the Web using a search engine. The approach is also applicable to other actors, such as famous persons, organizations or other multiple relational entities. For the second improvement of threshold tuning for inhomogeneous communities, we extract social networks among artists (contemporary), who participated in the International Triennale of Contemporary Art (Yokohama Triennale 2005) to facilitate the navigation of artists' information. The algorithm can identify even tenuous relations among the artists. We first describe the basic idea of extracting social networks from the Web; then indicate that objective rule-based methods do not function well when applied to inhomogeneous communities. We propose a subjective rule-based method that is inspired by network questionnaires in social science. Furthermore, we propose a more advanced algorithm, an objective and subjective rule-based method, which enables more exhaustive extraction than that available under the previous methods.

For the second topic, we provide an example of advanced utilization of social networks mined from the Web. We seek to learn a ranking model of entities from a social network that has been mined from the Web. We assume that the performance and power (i.e. ranking) of social actors are usually interpreted as relations and structural features embedded in the network. Therefore, the ranking of entities can be learned and predicted from the social network. For example, if we seek to rank companies by market value, we can extract the social network of the company from the Web, then discern and subsequently learn a ranking model based on the social network. Consequently, we can predict the ranking of a new company by mining its relations to other companies. We can learn from existing rankings to expect other rankings. Consequently, we can understand the kinds of relations that are important for what sorts of rankings; additionally, knowledge about the structural embeddedness (i.e. network features of entities) can improve the rankings. We can address various questions from the Web using our algorithm: Why are some companies successful and others are not? Why are some researchers more productive than others? Similarly to methods described in many existing studies of social network analysis, our algorithm is useful to uncover answers from a structural perspective rather than from an attributional perspective. The proposed model combines social network mining and ranking learning, which further uses multiple relations on the Web to explain arbitrary rankings in the real world. Moreover, we specifically examine a new approach to using Web information for advanced analysis by integrating multiple relations and network features of entities for interpreting rankings among them.

Our study will expand social network mining from the Web so that is applicable to various domains. Furthermore, results of our study will provide a bridge between relation extraction and ranking learning for advanced knowledge acquisition for use in Web Intelligence.

本論文は「Extraction and Application of Social Networks from World Wide Web(Webからの社会ネットワークの抽出及び応用)」と題し,英文8章から成る.第3~6章を第I部としてWebからの社会ネットワーク抽出の研究成果について記し,第7章を第II部として社会ネットワークの応用の研究成果を記している.

第1章は「Introduction(序論)」である.社会ネットワークはアクター(人物,会社や組織)をノードとして,アクター間に存在するつながりや関係を結んでネットワークとしたものであり,その分析は社会科学分野で行われてきた.Web上に大量の情報が公開されアクセス可能になったことで,Web情報から社会ネットワークを抽出し,分析,利用することがWebマイニングの一種として新しい研究が興ってきていることを述べ,本研究の貢献事項について記している.

第2章「Background and Existing Studies(背景と既存研究)」では,まず背景となる関係研究としてWebマイニング,Webからの情報抽出の状況を紹介している.次いで,社会ネットワークの抽出と分析の基礎となる考え方,技術について纏めている.

第3章「Problem Definition(問題設定)」では,Webからの社会ネットワーク抽出に関する関連研究について記し,既存手法の問題点について述べている.人間間関係抽出の典型的な既存手法では,2つのアクターを表すエンティティが1Webページ内で共起するWebページ数が多い程,関係が強いとの認識の下,Web検索エンジンのAND検索でこの共起回数を計測している.この第一の問題点は,例えば企業間関係の抽出では,2企業が良く知られた企業であるとこの2企業名のAND検索を発すると,ニュース文等を含め様々な文脈で非常に多数の共起ページ数が得られることになってしまい,抽出したい種別の関係の強さとはかけ離れた計測値になってしまう.第二の問題点は,共起Webページ数により関係強度を計測する既存手法は各アクターが異なる文脈でWebに現れるような,不均質性を有する社会コミュニティでの関係については,良く働かないことである.そして本研究では,第一の問題点に対して目的とする種別の関係に絞って強度を計測し,社会ネットワークを抽出する手法,第二の問題に対しては関係存在有無判定の閾値を状況毎に適応的に調整して,社会ネットワークを抽出する手法を提案していることを述べている.

第4章「Social Network Extraction for Complex Relations(複雑な関係に対する社会ネットワーク抽出)」では,第3章の第一の問題に対処する手法として,Webから企業間の特定の関係を関係識別手法を導入して抽出する手法を示している.基本的な考え方は,2企業名に加えて特定の関係を表す関係語(複数)も加えてAND検索し,そのヒット件数によりこの関係に焦点を当てた強度計測を可能にする.この検索に必要となる関係語は,最初に指定した関係語(以下に記す例では"提携"と"訴訟")とWebで共起頻度が高い語を,Jaccard係数に基づいて選定する方法を採っている.

以上の手法により,日本の電子情報企業60社を対象として提携関係(資本提携と業務提携あり),及び訴訟関係(係争段階と和解段階あり)について関係強度を求め,関係ネットワークを抽出している.関係語の使用法は,関係語無しのAND検索,最も重要度が高い関係語も加えたAND検索,2番目に重要度が高いと推定された関係語も加えたAND検索の結果を統合することにより,適合率,再現率の点で良い結果が得られることを示している.

第5章「Social Network Extraction for Inhomogeneous Communities(不均質コミュニティに対する社会ネットワーク抽出)」では,第3章の第二の問題に対処する手法として,Web上で永続的でない弱い社会関係を抽出するため,ネットワーク全体から見て弱い社会的関係であっても,あるアクターにとって相対的に強い関係となるアクターを,4つのパラメータを状況適応的に調整することにより抽出する手法を示している.ここでの4パラメータは,エッジを張るか否かを決めるオーバーラップ係数とマッチング係数の閾値2個と各ノードからのエッジの最小数に関する2パラメータである.本手法は2005年横浜トリエンナーレに参加した133名のアーティストの関係ネットワーク抽出に用いられ,ユーザをナビゲートするWebサイトとして実際に運用された.

第6章「General Model of Social Network Extraction(社会ネットワーク抽出の一般化モデル)」では,上記第4,5章の社会ネットワーク抽出の手法を纏めて,Webから様々なエンティティ間の社会ネットワークを抽出するための,汎用的枠組みを提示している.

第7章「Ranking Entities Based on the Social Network(社会ネットワークに基づくエンティティのランク付け)」では,社会ネットワークでの特徴が各ノードとなるエンティティの重要度ランキングの推定に利用できることを示している.特徴としては,ネットワーク中心性(次数中心性,近接中心性と媒介中心性を含む),複数の関係についてのネットワークの組合せ,到達可能ノード数や隣接ノードが持つ接続数などのネットワーク構造などであり,どのような特徴量がランキングに影響するかを,ランキングが得られているデータへの相関が最も高くなるような学習により定めている.第一のデータとしては,電子産業分野の312社について株式時価総額,社員の平均年間収入額,優れた企業についてのランキングデータを用いている.この場合に用いる複数ネットワークとしては,共起頻度に基づくネットワーク,業務提携ネットワーク,資本提携ネットワーク,同一株式市場ネットワーク,株保有関係ネットワークなどである.第二のデータとしては,東大の253名の教員について,発表論文数のランキングデータを用いている.この場合に用いる複数ネットワークとしては,日英についての共起頻度に基づくネットワーク,同一所属のネットワーク,同一プロジェクトのネットワークなどである.第二のデータの場合だと,日本語での検索ヒット数と英語で抽出した共起回数ネットワークでの次数中心性が,発表論文数と高い相関を有するなどの知見が得られたことを述べている.

第8章「Conclusion and Future Work(結論と今後の研究)」では,本論文の成果を纏め,今後の研究について言及している.

以上を要するに,本論文はWebマイニングの一種としてのWebからの社会ネットワーク抽出手法に関し,2つのアクターが各1Webページ内で共起する回数が多い程,関係が強いとする既存手法ではうまくいかない場合の問題に対処する手法を提示している.第一は,例えば企業間関係ネットワーク抽出では,2企業が良く知られた企業であるとAND検索を行うと様々な文脈で多数の共起ページ数が得られて,抽出したい特定の関係の強さとはかけ離れた計測値になってしまう問題に対し,抽出したい種別の関係語も付加してAND検索する手法である.第二は,各アクターが異なる文脈でWebに現れるような不均質なコミュニティに対しては,全体から見れば弱い社会的関係であっても,あるアクターにとっては相対的に強い関係となるアクターを,関係存在有無判定の閾値を状況毎に適応的に調整して取り上げ,社会ネットワークを抽出する手法である.以上の手法の有効性を実験を通して具体的に実証している.更に,このようなWebから抽出した社会ネットワークのネットワーク中心性といったような各種特徴量と,各エンティティの重要度のランキングの相関について実験的に検討し,このようなネットワーク特徴量が各エンティティの重要度ランキングの推定に利用できることを示している.これらの研究成果により,本論文は電子情報学上貢献するところが少なくない.

よって本論文は博士(情報理工学)の学位論文として合格と認められる.