1
© 2011 Columbia University
E6885 Network Science Lecture 3:
Network Representations and Characteristics
E 6885 Topics in Signal Processing -- Network Science
Ching-Yung Lin, Dept. of Electrical Engineering, Columbia University
September 26th, 2011
© 2011 Columbia University2 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Course Structure
Final Project Presentation 1412/19/11
Large-Scale Network Processing System 1312/12/11
Behavior Understanding and Cognitive Networks 1212/05/11
Privacy, Security, and Economy Issues in Networks 1111/28/11
Info Diffusion in Networks1011/21/11
Final Project Proposal Presentation911/14/11
Dynamic Networks810/31/11
Network Topology Inference710/24/11
Network Modeling610/17/11
Network Sampling and Estimation510/10/11
Network Visualization410/03/11
Network Partitioning, Clustering, and Use Case of Characteristics309/26/11
Network Representations and Characteristics209/19/11
Overview – Social, Information, and Cognitive Network Analysis109/12/11
Topics Covered
Class
Number
Class
Date
2
© 2011 Columbia University3 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Graph Partitioning
� Many uses of graph partitioning:
–E.g., community structure in social networks
� A cohesive subset of vertices generally is taken to refer to a subset of vertices that
– (1) are well connected among themselves, and
– (2) are relatively well separated from the remaining vertices
� Graph partitioning algorithms typically seek a partition of the vertex set of a graph
in such a manner that the sets E( Ck , Ck’ ) of edges connecting vertices in Ck to
vertices in Ck’ are relatively small in size compared to the sets E(Ck) = E( Ck , Ck’ )
of edges connecting vertices within Ck’ .
© 2011 Columbia University4 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Example: Karate Club Network
3
© 2011 Columbia University5 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Hierarchical Clustering Algorithms Types
� Primarily differ in [Jain et. al. 1999]:
– (1) how they evaluate the quality of proposed clusters, and
– (2) the algorithms by which they seek to optimze that quality.
� Agglomerative: successive coarsening of parittions through the process of
merging.
� Divisive: successive refinement of partitions through the process of splitting.
� At each stage, the current candidate partition is modified in a way that minizes a
specific measure of cost.
� In agglomerative methods, the least costly merge of two previously existing
partition elements is executed
� In divisive methods, it is the least costly split of a single existing partition element
into two that is executed.
© 2011 Columbia University6 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Hierarchical Clustering
� The resulting hierarchy typically is represented in the form of a tree, called a
dendrogram.
� The measure of cost incorporated into a hierarchical clustering method used in
graph partitioning should reflect our sense of what defines a ‘cohesive’ subset of
vertices.
� In agglomerative algorithms, given two sets of vertices C1 and C2, two standard
approaches to assigning a similarity value to this pair of sets is to use the
maximum (called single-linkage) or the minimum (called complete linkage) of the
dissimilarity xij over all pairs.
� Dissimlarities for subsets of vertices were calculated from the xij using the
extension of Ward (1963)’s method and the lengths of the branches in the
dendrogram are in relative proportion to the changes in dissimilarity.
( ) ( 1)
i jv v
ij
v v
N N
x
d N d N
∆
=
+ −
xij is the “normalized” number of neighbors of vi and vj that are not shared.
Nv is the set of neighbors of a vertex.
∆ is the symmetric difference of two
sets which is the set of elements that
are in one or the other but not both.
4
© 2011 Columbia University7 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Other dissimilarity measures
� There are various other common choices of dissimilarity measures, such
as:
2
,
( )ij ik jk
k i j
x A A
≠
= −∑
� Hierarchical clustering algorithms based on dissimilarities of this sort are
reasonably efficient, running in time.2( log )v vO N N
© 2011 Columbia University8 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Hierarchical Clustering Example
5
© 2011 Columbia University9 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Spectral Clustering
� Finding the eigenvectors of the adjacency matrix
� Starting with the largest (absolute) eigenvalues, the entries of each
eigenvector are sorted.
� The vertices corresponding to particularly large or negative entries, in
conjunction with their immediate neighbors, are declared to be a cluster.
� The motivation is the fact that, in the case of a graph consisting of two d-
regular graphs joined to each other by just a handful of vertices, the two
largest eigenvalues will be roughly equal to d, and the remaining
eigenvalues will be of only O(d1/2) in magnitude � a gap in the spectrum
of eigenvalues – a spectral gap.
iλ=i iAx x where 1 vNλ λ≤ ≤⋯
© 2011 Columbia University10 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Spectral clustering – cont’d
� The two eigenvectors corresponding to the largest two eigenvalues can be
expected to have large positive entries on vertices of one sub-network and large
negative entries on vertices of the other sub-network.
� In the Karate Club Network example, the first eigenvector appears to suggest a
separation of the 1st and 34th actors, and some of their nearest neighbors from the
rest of the actors.
� The second eigenvector in turn provides evidence that these two actors, and
certain of their neighbors, should themselves be separated.
6
© 2011 Columbia University11 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Spectral Analysis Example
© 2011 Columbia University12 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Spectral Partitioning involves iterative bisection
� The smallest eigenvalue of the Laplacian matrix can be shown to be
identically equal to zero. If we suspect a graph G to consist of nearly 2
components, we should expect the second smallest eigenvalue λ2 to be
close to zero.
� Fiedler, 1973, suggested partitioning vertices by separating them
according to the sign of their entries in the corresponding eigenvector x2.
� The vector x2 is hence often called the Fiedler vector, and the
corresponding eigenvalue λ2 , the Fiedler value, which is also known as
the algebraic connectivity of the graph.
7
© 2011 Columbia University13 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Spectral Bisection Example based on Fielder Vector
© 2011 Columbia University14 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Case Study
8
© 2011 Columbia University15 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Network Mining for
Company Value Prediction
04/23/2010
Yingzi Jin and Ching-Yung Lin
Social and Cognitive Network Science Researches
IBM T. J. Watson Research Center
© 2011 Columbia University16 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Outline
� Background and Study goal
� Infer Company Networks from Public News
� Network Feature Generation & Selection
� Predict Company Value
� Conclusion and Future work
9
© 2011 Columbia University17 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
� An Analytics research field since 1920s.
� Social Networks (SNs)
Nodes : Actors (persons, companies, organizations etc.)
Ties : Relations (friendship, collaboration, alliance etc.)
� Network properties
– Degree, distance, centrality, and various kinds of positional and equivalence
� Application of SNs
– Social psychology: analyzing social phenomena
– Economics: consulting business strategy
– Information science: Information sharing and recommendation, trust
calculation, ontology construction
Social Network Analysis
�Web 2.0 Social Networking is a special form -- subscription network!!
� Analysts are mostly more interested in finding the real/intrinsic networks!! 17
© 2011 Columbia University18 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Company Value Analysis
� Accounting-based financial statement information
– Fundamental values:
ROE(Return On Equity), ROA(Return On Asset), PER(Price Earnings Ratio),
PBR(Price Book-value Ratio), Employee Number, Dividend Yield, Capital Ratio,
Capital, etc.
E.g. “Fundamental Analysis, Future Earnings and Stock Prices”,
[Abarbane&Bushee97]
� Applying historical trends to predict stock market index (Heng Seng
Index in Hong Kong)
E.g. “Support Vector Machine Regression for Volatile Stock Market Prediction”
[H.Yang02]
)...(ˆ 1−− ++= twtt IIfI
18
10
© 2011 Columbia University19 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Social Network Analysis of Companies
� Social Network Analysis
Based on relations and structures (i.e. embeddedness) to explore power and
positional priorities of company
E.g.
“Social Structure and Competition in Interfirm Networks: The paradox of
Embeddedness” [Uzzi97]
“Relationships of Cooperation and Competition between Competitors”
[Bengtsson03]
“The Firm as Social Networks: An Organizational Perspective” [H.Wai05]
19
© 2011 Columbia University20 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
A new Analytics paradigm –
Are Social Networks of Companies related to Companies’ Value?
20
11
©2011 Columbia University21 E6885 Network Science –Lecture 3: Network Partitioning, Clustering, and Use Case
W hat are our research goals?
Finding answers of,
Is it possible to predicta com pany’s profit or revenue changes based
on dynam ic com pany networks?
How can we inferevolutionary company networks from public news?
� How accurate can network characteristics help predicting
profit/revenue changes?
� What are the most important – positive or negative – feature
measures of networks to predict profit/revenue?
21
© 2011 Columbia University22 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Outline
� Background and Study goal
� Infer Company Networks from Public News
� Network Feature Generation & Selection
� Predict Company Value
� Conclusion and Future work
12
©2011 Columbia University23 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Company Relationship Detection
Specific Relation
Cooperation, competition, acquisition, incorporation, supply
chain, stock share…
“Extracting Inter-business Relationship from World Wide Web” [Jin08]
“Temporal Company Relation Extraction” [Changjian09]
– Focus on details, deeper NLP
– Rare events, sparse, ad-hoc
� Generic Relation
– Who give me more impact [in a period]? (maybe
positive or negative)
– Comprehensive, dynamic relations (like Google rank)
– Shallow NLP, easy to get weighted and directed
networks, much more events.
� THIS WORK!
23
© 2011 Columbia University24 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Generic Relation Extraction
� Basic Idea:
– For each company x, we extract companies who
• Frequently co-appear with x in x’s important financial articles
• Frequently mentioned together with x in important sentences
In a period of time (e.g. one year)
SentenceArticle (document)
24
13
© 2011 Columbia University25 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Example (from NYT 2009 articles about I.B.M)
About 300 articles mentioned I.B.M.
*International Business Machines* (84 articles), *I.B.M.* (277 articles)
� I.B.M. -- Microsoft (55 articles, 264 sentences, weight=85.85455)
http://www.nytimes.com/2009/03/06/business/06layoffs.html
Two days after I.B.M.'s report, Microsoft said that its quarterly profits were disappointing.
http://www.nytimes.com/2009/05/07/technology/07iht-telecoms.html
... the world's largest software makers, including Microsoft, SAP and I.B.M., which...
http://www.nytimes.com/2009/01/31/business/31nocera.html
Caterpillar, Kodak, Home Depot, I.B.M., even mighty Microsoft they are all cutting jobs.
http://www.nytimes.com/2009/03/23/technology/companies/23mainframe.html
More recently, Sun Microsystems, Hewlett-Packard and Microsoft have made mostly
unsuccessful attempts to have made mostly unsuccessful attempts to pull mainframe
customers away from I.B.M. by ...
� I.B.M. -- SPSS (1 articles, 9 sentences, weight=13.675)
http://www.nytimes.com/2009/07/29/technology/companies/29ibm.html
I.B.M.to Buy SPSS, a Maker of Business Software
I.B.M.'s $50-a-share cash offer is a premium of more than 40 percent over SPSS's closing
stock price on Monday.
I.B.M.took a big step to expand its fast-growing stable of data analysis offerings by
agreeing on Tuesday to pay $1.2 billion to buy SPSS Inc.,...
� I.B.M. -- Nike. (4 articles, 9 sentences, weight=8.212)
http://www.nytimes.com/2009/01/22/business/22pepsi.html
… companies that have taken steps to reduce carbon emissions includes I.B.M., Nike,
Coca-Cola and BP, the oil giant.
http://www.nytimes.com/2009/11/01/business/01proto.html
Others are water-based shoe adhesives from Nike and a packing insert from I.B.M.
25
© 2011 Columbia University26 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Generic Relation Extraction
Title: x……
…x.. …y1. .. ..
…….y3………
……………y4..
Document Weight Sentence Weight
S1: x ….. y1 …
S2: x… y3…..y5
S3: y3..x…, y4…y1…
• |Y|: How many
companies on the article?
• ΣtfxY: How many times
companies appeared?
• tfxHow many times “x”
company appear?
• w: Does names
appeared on the title?
• |Y1|: the number of
company names
appeared in the same
sentence.
• |Y2|: the number of
company names
appeared between “x”
and “y”
∑ ∈
×+=
Yy yx
x
i i
tfw
tfw
Y ,
d
*
*
)
||
1
1log(w
∑∑ ×⋅+×⋅= sd www sfbdfa
)
||
1
||
1
1log(w
21
s
YY
++=
For target company “x”, first download NYT articles for a year, and select candidate
companies Y={y1,y2,…} appeared on the articles, then calculate each candidate
company’s relation strength with “x”.
26
Choose articles in a period
Target company x as query
Download articles
details
26
14
© 2011 Columbia University27 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Data and Network
� Data Source:
– Relationships among companies from public articles
• New York Times (NYT) articles: 1981 ~ 2009
http://www.nytimes.com/
• 7594 companies
http://topics.nytimes.com/topics/news/business/companies/index.html
– Company Values: profit, revenue, etc.
• Fortune 500: 1955-2009
http://money.cnn.com/magazines/fortune/fortune500/2009/full_list/
� Target companies:
– 308 companies (from NYT & Fortune500)
– 656,115 articles about target companies:
xxTarget
company
Bootstrap approach27
y
27
© 2011 Columbia University28 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Network size (all)
28
year #nodes #edges year #nodes #edges
1981 463 4030 1996 1202 46265
1982 478 4457 1997 1266 45650
1983 477 4546 1998 1312 51362
1984 484 4606 1999 1379 53653
1985 546 6606 2000 1534 59079
1986 565 6680 2001 1496 55801
1987 941 124326 2002 1487 54713
1988 1015 108075 2003 1504 54173
1989 1066 132906 2004 1461 51801
1990 1070 177022 2005 1193 43944
1991 1080 107973 2006 1355 51896
1992 1125 53625 2007 1280 44501
1993 1133 136807 2008 1260 43340
1994 1147 130975 2009 1203 37921
1995 1134 52855
28
Financial
Crisis
1987
15
© 2011 Columbia University29 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Different Threshold Network
0
1
2
3
4
5
6
7
a
ll
1
0
0
_
3
0
1
0
0
_
2
0
1
0
0
_
1
0
1
0
0
_
6
5
0
_
3
0
5
0
_
2
0
5
0
_
1
0
5
0
_
6
5
0
_
2
3
0
_
2
0
3
0
_
1
0
3
0
_
6
3
0
_
2
2
0
_
1
0
2
0
_
6
2
0
_
2
1
0
_
6
1
0
_
2
T1_T2
F
e
a
tu
re
E
ff
e
c
ti
o
n
revenue
profit
delta-revenue
MEAN
Thresholding of Networks
x
T1
T2
T1=20
T2=10
29
29
© 2011 Columbia University30 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Comparison of Naïve co-occurrence and the proposed method
30
Dominated by big/general companies Better balance between different company sizes
� IBM 1995 (doc coocurrence) � IBM 1995(new algorithm – doc
weights + sentence weights )
16
© 2011 Columbia University31 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Example of Network Evolution (IBM)
� IBM 2009� IBM 2003
31
31
© 2011 Columbia University32 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Example of Network Evolution (Microsoft)
� Microsoft 2003� Microsoft 1995
1995199519951995 2003200320032003 2009200920092009
1 IntuitIntuitIntuitIntuit I.B.M.I.B.M.I.B.M.I.B.M. GoogleGoogleGoogleGoogle
2 I.B.M. Apple Apple
3 Intel Intel Intel.
4 Apple Time Warner Sony
5 Novell Sony I.B.M.
32
� Microsoft 2009
17
© 2011 Columbia University33 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Outline
� Background and Study goal
� Infer Company Networks from Public News
� Network Feature Generation & Selection
� Predict Company Value
� Conclusion and Future work
© 2011 Columbia University34 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
xx
w w
w
w
w
w
w
w
w
Weighted-Undirected
Network
Binary -Directed
Network
Binary -Undirected
Network
Weighted-Directed
Network
Y
w
w
W w
z
w
xx
w
1
w
w
w
w
w
w
7 w
YW
W W
zw x
x
Y
z xx
Y
z
Network Type
W i-j = W i->j + W j->i
34
34
18
© 2011 Columbia University35 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Network Feature Generation (1/3)
Who give company x impact?
– Neighbor companies on the network
– Reachable companies on the network
Network Features:
– number of neighbors (In-degree, Out-degree)
– number of reachable nodes
– number of connections among neighbors
– number of connections among reachable nodes
– neighbors’ degree (In-degree, Out-degree)
– distance of x to all reachable nodes
– distances among neighbors
– ratio of above values between neighbors and reachable nodes …
– etc.
*(Normalize by network size)
x
Generate 57 Network features from weighted/binary,
directional/undirectional networks
35
35
Neighbor
companies
Reachable
companies
© 2011 Columbia University36 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Network Feature Generation (2/3)
Temporal Network Features:
– number of neighbors (In-degree, Out-degree) last year (or w
years ago)
– number of connections among neighbors last year (or w
years ago)
– number of connections among reachable nodes last year (or
w years ago)
– number of neighbors degree last year (or w years ago)
– distance of x to all reachable nodes last year (or w years
ago)
– … etc.
After 5 years
After 10 years
Similar to,
• What’s last year’s (or w years ago) revenue?
• What’s last year’s (or w years ago) profit?
36
57×Window temporal network features
19
© 2011 Columbia University37 E6885 Network Science – Lecture 3: Network Partitioning, Clustering, and Use Case
Network Feature Generation (3/3)
Delta Change of Network Features:
– Delta change of the number of neighbo
本文档为【NetSci-Fall2011-Lecture3】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。