Networks in their Surrounding Contexts

Homophily Test

计算不同category相连edge比例 与 理论比例的大小关系。如果”significantly less than”，那么就叫做同质化。

Conv sppedup

Accurate compu

Approximatation computation

Low-rank

sparse

Activation function (ReLU)

Yuzhe

$min\sum||Y_i-r((A+B)\cdot X_i)||_F^2, st.rank(A)<T_1, ||B||_0<T_2$

A is a low-rank tensor, while B is a sparse tensor

Speaker:

1	`Prof. Xiang Chen`

Low power

power barrier ( battery capacity size)

OLED

• 不同颜色能耗比不同，相比降低亮度，可以增加红绿的比例（oled）
• 对不同label的视频（游戏，电影，新闻——。。）可以有不同的处理方式。

GPS:

• 不持续发送信号

GPU

• fps： 手机越小，距离越大。需求越小。GGG
  • 距离：用camera（间歇性）+sensor(持续性)

DNN

• FC （ memory sensitive）
  • sparsity -> cluster?
• CNN(computational sensitive)
  • layer partition of different nodes(distributed computation)

Mobile security

• Gesture (velocity pressure area) is different

Continuous Random Variables/Distributions

Exponential

Gamma

Normal

Chi-square

typical type of Gamma, $\alpha = r/2, \theta = 2 = 1/\lambda$

where r is called the degree of freedom

eg: Brown motion: $x = Normal,y = Normal, then, r = \sqrt{x^2 + y^2} = \sqrt{chi-square}$

Pareto distribution

$\alpha$ = power (decay) law

Future

• Processor
  • many cores
  • heterogeneous(APU)/specialized(AI chips) hardware
• Disk dead. Locality is still the king.
• Cluster as a personal supercomputer

Questions

• Can software system fully optimize for the hw
• How to decide which hw is suitable for a new sw
• How to transform a hw into a practical sw use

Challenge 1 -> Q1

• Parallel alh design
• HW features

C2 from prototype to production

• practical / technical constrains
  • hw: power,space,costs
  • sw: maintenance
  • workload: deep learning

C3 millions of lines of legacy code

how to solve: modular code?

一位local女教授，既Jimmy之后第二位不准手机铃声的教授。。。

第一节课是拿一个英文的科普视频 放一段讲一段。。。太真实了吧？。。。

C1 Strong and Weak ties 17

Basic definition

Path

• A path in a graph is a sequence of nodes with the property that each consecutive pair in the sequence is connected by an edge.
• A path can have repeat nodes;
• Path without repeat nodes is a simple path

Cycle

A cycle is a path with at least three edges, in which the first and last nodes are the same, but otherwise all nodes are distinct.

Bridge

the edge joining two nodes if deleting that edge would cause the two nodes in two different components.

Local Bridge

Bridge is rare

the edge joining nodes A and B, if its endpoints A and B have no friends in common.

Span of a local bridge:

the distance between the end points if that edge were deleted.(original:1)

Embeddedness(edge)

Embeddedness of an edge in a network is the number of common neighbors the two endpoints have.

Embeddedness(Local bridge) =0

Structure hole (几个不同contacts的中间人)

• access information originating in multiple, non-interacting parts of the network.
• have opportunities for innovations arose from the unexpected synthesis of multiple ideas, each of them on their own perhaps well-known, but well-known in distinct and unrelated bodies of expertise.
• have an opportunity for a kind of social “gate-keeping”; a source of power in the organization.

Connected

A graph is connected if for every pair of nodes, there is a path between them

Traffic in a Network

For each pair of nodes A and B: 1 unit of traffic “flow” from A to B if A and B belong to same component. the flow divides itself evenly along all the possible shortest paths from A to B

Betweenness

• Edge: total amount of flow that the edge carries, counting flow between all pairs of nodes using this edge.
• Node: total amount of flow that the node carries, when a unit of flow between each pair of nodes is divided up evenly over shortest paths

Triadic closure

朋友的朋友更容易成为朋友

cluster coefficient(a)

a的朋友们也互相是朋友的概率

Strong Triadic Closure Property

如果a 和bc关系很好，那么bc会成为朋友。

如果不是(no matter strong or weak)，violate the property

Strength of weak ties

neighborhood overlap (edge)

no of nodes who are neighbors of both A and B**/** no of nodes who are neighbors of at least one of A of B.

• Neighborhood overlap increases with the strength
• Local level : tie strength increases with neighborhood
• Global level : weak ties serve to link together different tightly-knit communities ?

Weak ties provide the more crucial(关键) connective structure
• for holding together disparate communities and
• for keeping the global structure of the giant components intact.

Graph patitioning

division

移除最可能连接两大块的（betweenness最大值）

agglomerative(凝聚)

把nodes that are likely to belong to the same region merge起来

Girvan-Newman Method

• Find the edge of highest betweenness and remove these edges from the graph.
• Recalculate all betweennesses, again remove the edge or edges of highest betweenness.

C2 Networks in their Surrounding Contexts

Homophily

The tendency of individuals to associate and bond with similar others

Friendship that forms because two people

• have a common friend (intrinsic network structure, triadic closure)
• attend the same school or work for the same company (contextual factor)情境因素

Measuring Homophily

Homophily Test: If the fraction of cross-gender edges is significantly less than 2pq(p = fraction of males,q = fraction of females), then there is evidence for homophily.

The edge is heterogeneous(异质) if two end nodes do not share the same characteristic

Mechanisms Underlying Homophily

Selection

select friends with similar characteristic. tends to drive the network towards smaller clusters of like-minded individuals (balkanization)

• individual characteristics drive the formation of links (邻居)
• involves immutable(不变) characteristics (determined at birth)
• 物以类聚。

Socialization and social influence

modify their behaviors to bring them more closely into alignment with the behaviors of their friends.

– reverse of selection
– Involves mutable characteristics
– 近朱者赤， 近墨者黑/lies down with dogs, rises with fleas

Social influence

can produce network-wide uniformity, as new behavior spreads across the links.

Affiliation(联系) Networks 17

Include the contextual factors (the set of activities) into the network. expressed as a bipartite(even)
graph.

• node: person or focus(activity)
• edge: (person,focus)

• A graph is bipartite if its nodes can be divided into two sets in such a way that every edge connects a node in one set to a node in the other set

• Two people sharing the same focus → an opportunity to become friends.

Extension:

• Node: person/focus
• edge: (person,focus) or (person person)

3 Closure Processes

• Triadic closure: 朋友的朋友更容易成为朋友
• Membership closure(social influence): 朋友参加的活动更容易参加
• Focal closure (selction): 一个活动中的两人更容易成为朋友

Tracking Link Formation

1. – For each k, identify all pairs of nodes who have exactly k friends in common, but who are not directly connected by an edge.
2. (Difference time with step1 ) T (k) = the fraction of these pairs that have formed an edge.

• Triadic Closure： HIGH comon friends -> higher fraction
• Focal closure: high -> not so high

The Schelling Model

How global patterns of spatial segregation can arise from the effect of homophily operating at a local level (Thomas Schelling)

• Each agent(population) wants to have at least t agents of its own type as neighbors
• Unsatisfied agents: – fewer than t neighbors of the same type as itself and move to a new cell

homophily draws people together along immutable characteristics

The Schelling model creates a natural tendency for mutable characteristics

C3 Positive and Negative Relationships

clique/complete graph: graph which an edge connecting each pair of nodes

• Balanced Structure(triangle)
  • Three mutual(相互的) friends
  • A third mutual enemy
• Unbalanced Structure(triangle)
  • A,和BC 玩的好。BC仇敌。
  • All are enermies

A complete graph is structurally balanced if its everyone triangle is balanced.

Balance Theorem

If a labeled complete graph is balanced, then

• either all pairs of nodes are friends,
• or else the nodes can be divided into two groups, X and Y ,

Weak Structural Balance Property:

There is no set of three nodes such that the edges among them consist of exactly two positive edges and one negative edge . ( all are enermy are possible)

Structural Balance in Arbitrary (Non-Complete) Networks

A signed graph is balanced if and only if it contains no cycle with an odd number of negative edges.

Searching for balanced division

• find the connected components using positive edges. Declare each component to be a supernode.
• the supernodes form the reduced graph (negative edges only)
• BFS: edges connect two nodes in the same layer: a cycle with odd number of nodes

Generalizing the Definition of Structural Balance

Approximately Balance Theorem

If at least 99.9% (1-$\epsilon$)of all triangles in a labeled complete graph are balanced, then

• either there is a set consisting of at least 90%(1-$\epsilon^{1/3}$)of the nodes in which at least 90% of all pairs are friends
• or else the nodes can be divided into two groups, X and Y ,
  • at least 90% of the pairs in X like each other
  • at least 90% of the pairs in Y like each other, and
  • at least 90% of the pairs with one end in X and the other end in Y are enemies.

C4 Information cascade 17

Reasons why individual might imitate the behavior of others

• – Informational effect :

  • The behavior of others conveys information about what they know
  • Peer pressure
  • Imitate what others (e.g. idols) are doing

• Network effect (direct benefit effect) :(C5)

  you incur an explicit benefit when you align behavior with the behavior of others.

Bayes Rule

$P(A|B) = \frac{A\cap B}{B}=\frac{P(A)P(B|A)}{P(B)}$, 一般 ，pa, p(b|a)题目都给了。问题是求pb：

若A好算:$p(b) = P(A)P(B|A)+P(A^c)P(B|A^C)$

A Simple General Cascade Model 17

• States: G(Good) with probability p, and B with 1-p

• Accepting select which state

• Private information

• Signal H(High) before making decision: accepting is a good idea, L(Low) : bad idea

  P(H|G) = q > 0.5, P(L|G) = 1-q < 0.5

• Payoff: 0 reject. Vg: accepting a good option Vb: accept a bad option

Suppose one receives a H signal

• Expected payoff = Vg * P(G|H) + Vb *P(B|H)
• P(G|H) = $\frac{p(G)p(H|G)}{p(G)p(H|G)+p(B)p(H|B)}= \frac{pq}{pq+(1-p)(1-q)} >p$

Multiple signals

S = a high signals + b low signals

• posterior probability Pr [G | S] is greater than the prior Pr [G] (p) when a > b;

C5 Network Effects

Externalities（和外部坏境联系的场景 如 交通事故？party）

situation that the welfare of an individual is affected by the actions of other individuals

• Positive: welfare increases when others are joining
• Negative: 相反。

Without network effect, only consider Reservation price

the max amount one is willing to pay for one unit of the good. If consumer x (0 ≤ x ≤ 1) has a higher reservation price r(x) than consumer y, then x < y.

**r: strictly decreasing **

p’: production cost of one unit of the good (the minimum price a producer is willing to accept to sell a good)

x’: equilibrium quantity of the good so that r(x’) = p’

The Economy with Network Effects

• intrinsic interest. r(x). eg. r(1 ) = 0

• the no. of other people using the good

  • ( z: fraction of people in use).
  • f(z) measures the benefit to each consumer from those who use the good.f(z) is increasing in z, f(0) = 0

• reservation price of consumer x = r(x)f(z) . here z is the fraction expected by x

• self-fulfilling expectations equilibrium p’ = r(z)f(z)

Stability, Instability, and Tipping Points

• 0 < z < z’ 买家不想买。“downward pressure” on the consumption of the good : this would push demand downward.
• z’ < z < z” 买家想买。 “upward pressure” on the consumption of the
  good: this would drive demand upward
• z” < z < 1 “downward pressure”
• z’ : critical point/tipping point

A Dynamic View of the Market

z^: fraction of population who buy the product (actual buyer)

r(z^)f(z) = p = >

z^ = $r^{-1}(p/f(z))$ = g(z)

For goods with network effects, the equilibria are typically not social optimal.(社会所有人的总利益)

Being the first to reach this tipping point is more important than being “best”.

Mixing Individual Effects with Population-Level Effects

f(Z) = 1 + az^2

r(X) = 1-x

C6 Power Laws and Rich-Get-Richer Models 17

Central Limit Theorem says that if we take any sequence of small independent random quantities, then in the limit their sum (or average) will be distributed according to the normal distribution.

A function that decreases as k to some fixed power, such as 1/k 2(fraction) is called a power law

Rich-Get-Richer Models

Model the growth of the popularity.

• Created pages in order : 1, 2, 3, . . . , j.
• When j is created, With probability p, page j, chooses a page i uniformly at random from among all earlier pages, and creates a link to this page i.
• With probability 1-p, page j creates a link to the page that i links to. (i also uniformly random distributed)
  • new version:with probability 1 − p, page j chooses a page l with probability
    proportional to l ’s current number of in-links, and creates a link to l.

preferential attachment: : “preferentially” to pages that already have high popularity. (人们更愿意打开已经火了的页面,copy别人的)

No. of in-links of node j = $x_j = p/q[(t/j)^q-1]$ . t: simulated steps. q = 1-p

At time t, we have nodes x1, x2, … xt. The fraction of nodes with at least k links is

$[\frac{q}{p}k +1]^{-1/q}$

f(k) = the fraction of nodes with exactly k links = $1/p [1+\frac{1-p}{p}k]^{-(1+\frac{1}{1-p})}$. when p -0, power law exponent is 2.

The long tail

a small set of items that are enormously popular

Zipf’s Law : the frequency of the j th most common word in English (or most other widespread human languages) is proportional to 1/j.

C6 Cascading behavior in networks 17

Structure of the network and how individuals are influenced by their particular network neighbors (instead of everyone else in C5)

Why an innovation can fail to spread through a population ?

• tightly-knit(严密) social community;
• complexity
• observability observe别人也在用
• trialability 可试验性。（一步一步慢慢来）
• compatibility with social system

the set of initial adopters causes a complete cascade at threshold q(大于百分之多少才换）.

cluster of density p

cluster of density p = a set of nodes such that each node in the set has at least a p fraction of its network neighbors in the set.

cluster of density 1:

The Relationship between Clusters and Cascades

• If the remaining network contains a cluster of density greater than 1 − q, then the set of initial adopters will not cause a complete cascade.(cluster 是cascade的阻碍 必要条件)
• Moreover, whenever a set of initial adopters does not cause a complete cascade with threshold q, the remaining network must contain a cluster of density greater than 1 − q（充分条件）

Extensions of the Basic Cascade Model 17

Heterogeneous Thresholds： each node has a specific payoff and hence threshold

A blocking cluster in the network is a set of nodes for which each node v has more than a 1 − qv fraction of its friends also in the set.

cascade capacity of the network: 有限初始集能造成complete cascade的最大threshold

最大值：1/2

proof number of AB edges is decreasing when switching w from B to A

payoff from choosing A = a’（两边都是A/AB) 则double a
payoff from choosing B = b’
payoff from choosing AB= a’+b’-c

C7 Small World Phenomenon

Watts-Strogatz model

Two type of links:

Homophily(和其他r个小格内点相连的link)and

Weak ties(剩余的k 个远link).

• d(v, w) :the number of grid steps between nodes v and w
• Probability of an edge is proportional to d(v, w)^-q (Small q, more long distances edges)

time: at most a2(log n)^2

A Rough Calculation Motivating the Inverse-Square Network

The probability that a random edge from center point v links into any node in this group is approximately independent of the value of d. ( in d - 2d circles)

Rank-Based Friendship

rank(w) = the number of other nodes that are closer to v than w is. (比w 还离v近一点的)

social distance

dist(v, w) = the social distance between nodes v and w = the size of the smallest focus that contains both v and w

A link between each pair of nodes v and w with probability proportional to dist(v,w)^-p

Efficient decentralized search when p = 1. 17

C8 Epidemics

•The basic reproductive number ( R0) = the expected number of new cases of the disease caused by a single individual = p(probability)k(new meet num).

Percolation : static view of the model. edge v-w is open is w is infected by v

SIR . susceptible infectious removed

SIS susceptible infectious back_TO_susceptile

SIRS susceptible infectious 免疫期 back_TO_susceptile

transient contacts — contact networks in which each edge is annotated with the period of time during which it existed

Analysis of Branching Processes

qn = the probability that the epidemic survives for at least n waves

q∗ = qn when n is infinite = the probability that the epidemic persists indefinitely.

Wright-Fisher model

1. 每一代 N个人
2. 每个孩子都只有一个家长。一个家长可以有多个孩子也可能没有。

consider the time that k个个体是一个祖先

C9 Link Analysis and Web Search

• Ranking of web pages

Information Retrieval

1960s: Search repositories of newspaper articles, scientific papers, patents, legal abstracts, and other document collections in response to keyword queries.

vote by link 缺点：offtopic, criticism, advertisement

each page有两种score

authorities 权威网站 更新： 所有指向他的page的hub score和

hub 首页 更新 类似

1
2
3
4
5
6

initial are score = 1
select k steps
for i in k:
	update auth
	update hub
normalize hub and auth

(A-\lamda I)x = 0

\lamda = eigenvalue

x = eigenvector

pagerank

每个node指出k个，其value平均分k，到新的node。

最后把收到的value sum。

Scaling Factor

sum之后乘以一个factor 。 然后把factor多出来的那一部分均匀分给每个人。

Random walks

随便选一个。然后继续选out-going的。和pagerank思路一样。停在哪个page的概率和pagerank概率一样。

• 有相关text的超链接权重更高。
• 用户点击数据 更能反映是否相关。

C10 Sponsored Search Market

SPONSORED SEARCH AD:关键词

branding ad ：直接投放在网站上

contextual ad： 根据用户特征投放广告

拍卖

• The Second Price Sealed Auction 由出价最高的买家获得物品，但他只需要支付所有投标者中的第二高价。

click-through rates：（r_i) The number of clicks per hour it will receive

revenue(收入) v_j per click of advertiser j,

ri*vj = benifit

Matching Market

if the search engine knew all the advertisers’ valuations for clicks

For buyer:

$v_{ij}$ = valuation for item i by buyer j

$p_i$ = price announced by the seller

v- p 就是买家收益。

Market clearing prices 所有买家选到最赚的而且不冲突

Constructing the set of market clearing price

price先重置为0

将最多人要买的slot price 加一

重新计算

重新加一

直到可以market clearing

Vickrey-Clarke-Groves (VCG) mechanism

the advertisers’ valuations are not known

算没有 A 后 BC 收益。比如600

有A后BC收益 比如 200

那么A 需要支付 600-200

GSP

bi bids per click

GSP charges a cumulative price of ri bi+1 for slot i.

Nash equilibrium

The pair of strategies (S; T) is a Nash equilibrium if S is a best response to T, and T is a best response to S.

Best response: $P_1(S,T)>= P_1(S’,T)$ T: stratage of 2

STrict: 没有等于。

Dominant strategy： a strategy that is a best response to every strategy of Player 2.

A strictly dominant strategy .

这一年来眼睛经常感到疲倦，再加之镜腿断了，于是想要换个合适的眼镜。

换眼镜也是换出了很多学问，索性记录一下。

how to buy

第一件事是决定怎么买，参考网上各论坛建议，选了三种方案。

1. 淘宝镜片 + 淘宝镜架 + 香港验光

   • 优点，便宜，透明。明月全套250 + 验光100 + 深圳路费 50
   • 缺点，时间久，去深圳麻烦

2. 深圳眼镜

   • 优点，便宜，是批发市场
   • 缺点，不透明，容易被宰，验光不规范

3. 香港眼镜

   • 优点，眼光规范，方便，品牌货便宜
   • 缺点，一般货贵，容易被宰

因为镜腿断了，急着要用眼镜。而另外两个都有明显缺陷（淘宝太久，深圳太远而且怕被宰）

where to buy

决定在香港买眼镜后发现事情没那么简单。香港眼镜店对我来说也分了三种选择。

• 眼镜88，EGG等连锁店
• 写字楼 楼上铺
• 日本平价店铺 zoff

还能怎么办，一个一个比较，看呗。

另外在香港论坛查了许多，又恰逢发现小米有镜架（249），蓝光眼镜（99）卖。查了下都是钨钢材质，虽然听不懂但对小米的品质还是有信心的，于是买了个蓝光眼镜拆了镜片做镜框。（客服说99的镜框和249的镜架材质重量设计都一模一样= =，唯一区别是一个韩国，一个国产。。。）

镜架有了，一个一个去问镜片。

香港好的一点是，说我再去其他地方看看不会尴尬，店员都很爽快。

总共问了6个店子。

写字楼1号 巴黎眼镜店

熟人推荐，瑞士宝1.61非球面300+防蓝光200 = 500。在那才知道。。我戴了三年的眼镜。。。戴！反！了！

难！怪！一！直！头！晕！

难！怪！一！直！掉！镜！片！

写字楼2号 不知名眼镜店

只有一个说广东话的老头，这种看起来挺靠谱的。

阿波罗1.61非球面290+防蓝光200 = 490

写字楼3号 连锁眼镜仓库?

装修的和内地有点像，但是听到 依视路880？不确定听没听错。

眼镜88

DULUX1.61蓝光 = 700

依视路1.61蓝光 = 1300

EGG

豪雅？不确定是否为EGG特供。

1.61非球面600 + 蓝光100 = 700

1.67非球面900 + 蓝光0 = 900

ZOFF

一家日本的连锁平价眼镜，在香港很受欢迎。

因为暂时只在太古城有店，所以电话问了下。

1. 不支持单独配镜片
2. 镜片是自己zoff的。。。？
3. 1.61非球面480+ 蓝光280= 760 全套眼镜

最终看了下，大概就是一般品牌500，豪雅700值得考虑。又想了下豪雅这么便宜！还要什么飞机！淘宝上买镜片都不止这个价了。最终手机没电了，不想再来所以入手EGG豪雅。。

值得一提的是香港的验光确实多了些没体验过的环节，总的来说感觉上专业一点。

conclusion

遗憾:

最后买的有点仓库，没考虑几点:

• 是否为EGG豪雅特供镜片，如果是的话。。。
• 许多参数并没有了解询问，如片基，阿贝数，镜片材料
• 具体型号？现在才知道就算是正品豪雅(VP IP 等等）也有很多型号

不过总的来说觉得700验光+豪雅已经是很不错的了，具体是什么豪雅 后天就知道了（特意叮嘱了给我留着镜片包装）

更新

眼镜到手，试戴半天后效果特别好，真的看电脑久了不头晕了！不过也可能是之前一直是反的原因。

镜片包装也如约给我了：

1515759363478

包装上没有任何豪雅的资料，电话问了豪雅的人确定确实egg有用，找工作人员，工作人员加了我微信，说可以给我一个我自己镜片的豪雅证明，里面也会specify具体是哪一款豪雅镜片。

总之是一次特别棒的体验

更新

本着所有东西都要体验一下的高尚理想，这次(2019.10)配眼镜选了另外一种方法…网上听热门的 日本JINS网店 海淘。

因为自己海淘的挺多，加之性价比确实蛮高的，500+可以有一个1.74折射率的HOYA眼镜，还是钛金属的镜框（镜架是塑料。。）也是挺满意的说。

另外打算下次配眼镜要么去日本线下？顺便还可以去玩下。要么就去知乎的深圳眼镜热店。

生活就是折腾才有意思啊哈哈~

CUHK CSCI5030

instructor: XU Lei

来自 交大 的大佬教授。

大佬就是大佬，直接用中文。

四年来第一次上中问的专业课，感觉exciting。

Preface

Probability distributions

• Uniform
• Poisson
  • Discrete
  • Parameter: $\lambda$
  • $P(X = k) = \frac {e^{-\lambda}\lambda^k}{k!}$
• Normal
• t-dis???
• Chi-square 卡方分布
  • k个独立的标准正态分布变量的平方和
  • parameter:k
• Cauchy

Benford’s Law

$P(d) = log_{10}(d+1)-log_{10}(d)$, where d is the case that the first digit of the data is d

Ch 1

Sample space: $S$

event:

• subset of $S$
• measurable, (can assign a probability)
• subset is NOT event

Conditional Probability:

$P(A|B) = \frac{P(A\cap B)}{P(B)}$

Bayes theorem

$P(A) = \sum{P(A\cap B_i)}$

Now: We want to know: if A happened, what are the p of different B?

$P(B_j|A) = \frac{P(A\cap B_j)}{P(A)}$

$P(A\cap B_j) = P(A|B_j)P(B_j)$

Bayes theorem definition:

Consider a partition $B_j$ of $S$ and event $A$:

$P(B_j|A) = \frac{P(A\cap B_j)}{P(A)}= \frac{P(A|B_j)P(B_j)}{\sum{P(A|B_i)P(B_i)}}​$

Monty Hall Problem

$B_j = C_2|X_1, A = H_3|X_1$

Ch 2 Discrete Random Variables

Mean is the quantity a that minimizes $min_aE(X-a)^2$

Variance $(x-E(x))^2$

Moment generating function = mgf = summary of the overall random behavior

median $min_b |x-b|$

新的一年

惟愿此心无怨尤。