POLYPHONET:An Advanced Social Network
Extraction System from the Web
Yutaka Matsuo
National Institute ofAdvanced Industrial Science and Technology (AIST), Japan
J. Mori, K. Ishida, M. Hamasaki, H. Takeda, T. Nishimura, K. Hasida, andM. Ishizuka
Univ. of Tokyo and National Institute of Informatics
Yutaka Matsuo (AIST)Social networkRepresent relations (ties) among
persons (actors)
Important for

Semantic Web, knowledge
management, information retrieval,ubiquitous computing…
Our lives are enormously influenced byrelations to others.

Network data

Questionnaires in sociologySNS

“Please name your four closest friends”
Friendster, orkut, myspace, LiveJournal,
Yahoo!360…

FOAF documents
Web link analysis, citation analysis,
blog analysis…

Our approach: Web miningapproach using a search engine
A social network of WWW2006 organizers

Yutaka Matsuo (AIST)

Content Social network mining from the Web

Algorithms and evaluations
 Advanced algorithms
 POLYPHONET
Academic conference support system Future directions

Yutaka Matsuo (AIST)Extracted Social Network for JSAI community(Japan Society of Artificial Intelligence)

Yutaka Matsuo (AIST)

projectcoauthorshiplaboratory

Co-attendance to a conference

Yutaka Matsuo (AIST)How to make the network?
NodeGiven!

Conference participants / members of a society

We need a list of names and affiliations.

Automaticallyobtained!
Edge
Obtained by Web information.
 Using a search engine, the co-occurrence of two persons’name on the Web is measured.
 Relation types(Edge labels)

Coauthor, Lab, Proj, ConfAlso, keywords of each researcher, clusters of reserachers

Yutaka Matsuo (AIST)Two names
742 hits

Publication-> coauthorship

My homepageLaboratory page-> same laboratory relation
Yutaka Matsuo (AIST)Co-occurrence
In JP domain,“Yutaka Matsuo”(X) AND “Mitsuru Ishizuka”(Y1): 124 hits
“Yutaka Matsuo”(X) AND “Riichiro Mizoguchi”(Y2): 11 hits
Y1: 791 hits
Y2: 813 hits
X: 500 hits
Jaccard coefficient |X∩Y1| / |X ∪Y1| = 124 / (791+500-124) = 0.11
Jaccard coefficient |X∩Y2| / |X ∪Y2| = 11 / (813+500-11) = 0.08

X and Y1 is a stronger relation than X and Y2 !

Yutaka Matsuo (AIST)

Measures of co-occurrence
Matching coefficient Mutual Information
 Dice coefficient Jaccard coefficient Cosine
 Simpson coefficient(overlap coefficient)

|X∩Y|log N|X∩Y| / |X||Y|
2|X∩Y| / (|X|+|Y|)|X∩Y| / |X∪Y||X∩Y| / (√|X||Y|)|X∩Y| / min(|X|,|Y|)with a cutoff threshold on |X| and |Y|.
⎧ X ∩ Y min( X , Y ) if X > k and Y > kf ( X ,Y ) = ⎨0otherwise⎩

Yutaka Matsuo (AIST)Co-authorshipprobability
Probabilityof coauthorship

Which co-occurrence measure is good?
Co-oc value vs Coauthor probability
unstable
Problem:Famous persons tend to have too much edges

Good!

Simpson coefficient

Matching coefficientbumpProblem:
Low-hitcout persons tend to have too much edges.

Yutaka Matsuo (AIST) Dice coefficient

Jaccard coefficient
Evaluation for JSAI community [Matsuo04]

Related works on social network mining

Referral Web (H. Kautz et al, 1997)

A name is given as input
Retrieve the name, and extract other names.
Measure co-occurrence (by Jaccard coefficient), and invent edges.
Ego-centric network within 2-3 radius

Flink (P. Mika, 2004)
Email messages, publications, FOAF documents, and Web mining
Web mining part

Similar to Referral Web
Jaccard coefficient“Semantic Web OR Ontology” is added to a query for disambiguation.

A. McCallum et al. (2004-)

Identify people in e-mail messages, and find homepages
Links are placed between the owner of Web page and persons discovered on the page.

They also use co-occurrence on the entire WebE.g, find a path from Henry Kautz to Marvin Minsky

with name-disambiguation probability model

Other studies using co-occurrence information
[Harada04] [Faloutsos04] [Kees04]…

Yutaka Matsuo (AIST)Small pseudocodes
Among related studies, underlying procedures are similar
and very simple
 To enhance versatility, we describe in small pseudocodes.
 Two basic functions:

GoogleHit: returns hit count
GoogleTop: returns (k) retrieved documents

Yutaka Matsuo (AIST)X…Y…Y..

Name disambiguation

Node expansion

Yutaka Matsuo (AIST)

Content Social network mining from the Web

Algorithms and evaluations
 Advanced algorithms






A1: Types of relation
A2: Scalability
A3: Person-to-word co-occurrence

 POLYPHONET:

Academic conference support system Future directions

Yutaka Matsuo (AIST)A1: Types of relations


It is more useful if we recognize types of relations.
In JSAI case, we define four types (classes) of relations:







Coauthor: Co-author of a technical paper
Lab: Members of the same laboratory or research institute. It is notalways a coauthor-relation, but it is also a strong relationship.
Proj: Members of the same project or committee
Cof: Participants of the same conference or workshop

Multi-labels for an edge.

Text classification problem!!
Yutaka Matsuo (AIST)Evaluation
In JSAI case,

For JSAI2003 participants, 275 training samples and 200
evaluation samples are used. We use C4.5 as a learner.

Yutaka Matsuo (AIST)A2: Scalability
Too many queries to a search engineAssume we have n names. Then, nC2 , or O(n2) queries arenecessary.
For 500 people, 124,750 queries…
cf) Google API (1000 queries/day), Yahoo! API (5000/day)Distribution of Simpson coefficient

0: about 67%
0-0.2: about 98%

10000
9000
8000

# pairs

researcher pairs

7000
6000

A social network is sparse!!
5000
4000
3000
2000
1000
00

Yutaka Matsuo (AIST)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

overlap coefficient
Simpsonco-efficient

0.8

0.9

1

Idea for scalability
Filter out pairs of persons that seem to have no relation.
Apply GoogleCooc only for promising pairs investigating by
GoogleTop

Combination of GoogleCooc and GoogleTop
Yutaka Matsuo (AIST)Evaluation for JSAI case85% of queries are saved.

For 504 researchers, originally 126,253 queries: O(n2)By applying filtering, 19,182 queries: O(n)Correlation of overlap coefficient between former method and proposed method

Successfully
obtainedoverlap coefficientby proposed
Simpsoncoefficient
usingmethod
filtering

1r = 0.931

0.8

0.6

Few positive pairs are dropped

0.4

0.2

Dropped

OKBad!

00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

overlap coefficient by former method

0.80.9Simpson coefficient by the original method
Yutaka Matsuo (AIST)1A3: Word-to-person Co-occurrenceCo-occurrence of a person name and a word

Not a person and a person
Affiliation matrix: words (W) to persons (X) matrix
840

Affiliation matrix



Keyword extraction for a person
Clustering of persons

Yutaka Matsuo (AIST)

Adjacent matrix

Clustering of persons
Context similarity of persons
using an affiliation matrix

In JSAI case, We cluster 540 researchers into 30 groupsusing cosine similarity, andcomplete-link clustering.

Yutaka Matsuo (AIST)

Result of extracted researcher clusters
Cluster1 : 神嶌敏弘，角田祐一，新村昭好，岡崎直観，倉田岳人，村田剛志，相原健郎，豊田正史，久保山哲二，藤村滋，仲尾由雄，藤澤瑞樹，橋本泰一， 池原悟，徳永健伸，荒木健治，奥村学，鈴木雅実，熊本忠彦，太田公子，
NLP
徳久雅人，村上仁一，賀沢秀人，岩垣守彦，川野洋，藪内佳孝，峯松信明，嵯峨山茂樹，西本卓也，中沢正幸，新田恒雄，桐山伸也，駒谷和範，伊藤敏彦，桂田浩一，天野成昭，中川聖一，古塩貴行，池ヶ谷有希，鈴木夕紀子，
野口靖浩，松本泰明，小玉智志
Weighted words: 自然言語(NLP)，音声(audio)，対話(dialogue)，言語(language)，抽出(extraction)，処理(processing)，クラスタリング(clustering)，生成(generation)，検索システム(retrieval system)，情報抽出

Cluster 2: 中西英之，角康之，間瀬健二，西本一志，藤城卓己，田森裕邦，安念克洋，天野竜太，櫻井晴章，岡夏樹，
Ubiquitous computing and robotics
今井倫太，田島敬士，畠山誠，大村英史，劉耿孟，上妻将文，楠本昌弘，大谷尚史，高畠政実，高橋昌史，小出義和，
岩澤昭一郎，伊藤禎宣，竹林洋一，堀聡，広瀬公太，小泉智史，矢入健久，木村春彦，青島大悟，雨宮陽介
Weighted words: インタラクション(interaction)、センサ(sensor)、ヒューマン(human)、ユビキタス(ubiquitous)、エージェント(agent)、コミュニケーション(communication)、ロボット(robot)、支援(support)、実装(implementation)

Cluster 10: 小出誠二，官上大輔，武田英明，和泉憲明，岩爪道昭，小路悠介，垂見晋也，來村徳信，古崎晃司，溝口Semantic Web理一郎，渡邉英一，池田満，酒井隆道，西原陽子，森田武史，見置孝昌，繁田佳宏，田中庸平，武内雅宇
Weighted words: オントロジー(Ontology)，支援環境(support environment)，知能(intelligence)，支援システム(support system)，学習支援(learning)，構築(development)，エージェント，設計，支援，人工Yutaka Matsuo (AIST)Keyword extraction
Using the person-to-word matrix, we can extract keywords for eachperson.



Example of keywords for D. Brickley

Comparison to standard document-to-word matrix (on retrieveddocuments): tf and tfidf

Yutaka Matsuo (AIST)For 567 JSAI researchers. For tf and tfidf, we collect 10 documents for each person.
Termex is used to recognize to recognize terms.

Content Social network mining from the WebAlgorithms and evaluations
 Advanced algorithms
Types of relation
Scalability
Person-to-word co-occurrence

 POLYPHONET:

Academic conference support system Future directions

Yutaka Matsuo (AIST)PolyphonetWeb-based system for an academic community

to facilitate communication and understanding of each otherbased on a social network extracted from the WebOperation


JSAI (the Japan Society of Artificial Intelligence) Annual Conferences(JSAI03-05), and International Conference on Ubiquitous Computing(UbiComp05)

JSAI2003

UbiComp05

Yutaka Matsuo (AIST)Polyphonet JSAI2005: Person view (Mypage)
Retrieval ofannotated comment
Yutaka Matsuo

Research clusterand Keywords
Social network

Acquintances(registered by users)
Strong relation
person (Web-mined)

His presentation

Presentation
bookmarks
Yutaka Matsuo (AIST)

Yutaka Matsuo (AIST)

Presentation view
Title and abstract

Add to my scheduleSocial network amongauthors and persons
who checked thepresentation

authors
Persons who checked
this presentation

other presentations
by the author

Yutaka Matsuo (AIST)Session view
Session title

presentations

Social network of authors
in the session

authors

Yutaka Matsuo (AIST)

Yutaka Matsuo (AIST)Yutaka Matsuo (AIST)

Yutaka Matsuo (AIST)In Ubiquitous Environment…
An IC card is distributed as a namecard in JSAI2005 and UbiComp05

A participant can also use his/her own IC card.

If two users put their cards…



Then, the two will be connected by a face-to-face link, resulting ina more connected social network during the conference.

Yutaka Matsuo (AIST)

Future directions


Mine structures of entities using a search engine
 Cross-field among AI, Web and social network analysis



Scalability
 Simple modules to be built up
 A goog combination of GoogleCooc and GoogleTop is necessary.
 As the Web grows…,


GoogleTop (which retrieves document and enables text analysis)gets less effective: it returns relatively smaller and smaller sizes ofWeb pages.


Sampling [Anagnostopoulos05,Bar-Yossef06] is important.

GoogleCooc yields a more precise number because the lowfrequency problem is improved.
Search engine for NLP [Cafarella05]

Yutaka Matsuo (AIST)

Module dependencies
AffiliationNetwork

NetworkRelation class

KeywordContexSim

GetSocialNet

ClassifyRelationExtractKeywords

GetSocialNetScalable

StructuralEquiv
ContexSimTop

GoogleCoocTop

GoogleTop: get top documents

GoogleCooc: get co-occurrence
GoogleCoocContext
ExpandPerson

GoogleHit: get hit count

GoogleA GoogleHit and GoogleTop provides a variety of modules though they are very simple

Yutaka Matsuo (AIST)

Relate-Identify process
We identify entities, extract relations of entities, and based on the wholenetwork structure and statistics, we improve the way to identify entities.
The process is repeated iteratively, and is gradually improved.
Initial data of persons- StructuralEquiv
X- Name disambiguation- Record linkage- Centrality, Clusteringtidenderovpm
I

Adjacent matrix
Xtion
ifica

IDENTIFY

Personal metadataName:
Affiliation:
Research topic:
Publication:- ExtractKeywords
Yutaka Matsuo (AIST)

Relation

RELATE- GetSocialNet- ClassifyRelation- ContextSim

tion
aler
racttxEW

X Affiliation matrix

For integration of multiple social networks, see
Y.matsuo et. al, “Spinning social networks for Semantic Web” to appear in AAAI-06

Conclusion
Social network extraction from the WebSmall modules using a search engine are built up for avariety of functions.
 Algorithms for types of relations, scalability, a person-toword matrix
Polyphonet
JSAI conference series(2003-06), and UbiComp05
 Many positive comments from participantsExtraction of structural information among entities
Scalability
 Identify-Relate processYutaka Matsuo (AIST)Thank you!
Yutaka Matsuoy.matsuo@aist.go.jp
National Institute of Advanced Industrial Science andTechnology (AIST)
AIST Office at AkihabaraThanks toMr. J. Mori, Dr. M. Hamasaki,
Mr. K. Ishida, Drs. T.Nishimura,
K. Hasida, and Prof. M. Ishizuka,and other colleagues.

Yutaka Matsuo (AIST)Name disambiguationCommunity-based approach“ubiquitous OR pervasive” for UbiComp community“Semantic Web OR Ontology”

Individual-based approach

We use affiliations for JSAI communityMany related works

Yutaka Matsuo (“University of Tokyo” OR “National institute of Advanced Industrial
Science and Technology” OR “AIST”）[Bekkerman05][Li05][Guha][Lloyd05][Marlin05][Mann03][Wacholder97]

Procedures
Retrieved by a query “X”
Cluster the results -> different clusters (hopefully) correspond to differentpersons


Similarity is defined using link structures, text similarities (or snippet similarities)

Obtain the characteristic keywords for the person X.

Yutaka Matsuo (AIST)

Proceedure
Retrieved pages by “X and Y”
Attributes
・Co-occurrence number of two persons ・Whether Simpson coefficient is over the threshold or not
・Number of X occurrence ・Number of Y occurrence・Either {publication, paper, presentation, activity, theme, award, author} is included in the title
・Either {member, laboratory, research institute, team} is included in the title
・Either {workshop, conference, seminar, meeting, sponsor, symposium} is included in the title
・・・・
・Either {publication, paper, presentation, activity, theme, award, author} is included in the first five line
・・・

Attributes of a page
(more than one, yes, yes, more than one, more than one, no, no, no, no, no, no, yes, no, no, no, yes, noClassification rule
NumCo = more_than_one → coauthor
NumCo = more_than_one & GroFFive(F)=no → laboratory(Rel=yes & GroTitle(E)=no & GroFFIve(C)=no → laboratory・・・・

Yutaka Matsuo (AIST)Class of relation: coauthor, laboratory, project, conferen