xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

扫码添加客服微信

扫描添加客服微信

留学生代写|Assignment代写 - CSCC46 Social and Information Networks

时间：2020-10-21

CSCC46 Social and Information Networks Fall 2020 University of Toronto Scarborough

CSCC46 Assignment 2

Instructions

• Your work must be your own.

• These problems require thought, but do not require long answers. Please be as concise as possible.

• This assignment is due by 2pm on Thursday, October 29. You may use up to two flex days to submit

the assignment late, meaning the hard deadline after which no late assignments will be accepted is

2pm Saturday, October 31.

• Your assignment must be typed; handwritten assignments will not be marked. You may use any word-

processing software you like (many academics use LaTeX). Figures can either be drawn electronically,

or you may hand-draw, take pictures, and include them as images in your submission. Whatever

word-processing you choose, please submit in PDF format.

• All assignments must be submitted electronically on MarkUs (see the course webpage for the MarkUs

link). Well before the due date, try submitting with MarkUs. You can submit an empty file as a

placeholder, and then submit a new version of the file later by using the “Replace” column. Check

that you have submitted the correct version of your file by downloading it from MarkUs.

Useful Mathematical Facts

This assignment is more rigorous than the previous one. Here are some mathematical facts that might be

useful.

• The Union Bound. This incredibly simple and intuitive fact comes in handy more often than you

might expect. It says that for any finite set of events, the probability that at least one of them happens

is no greater than the sum of the probabilities of the individual events:

P

(⋃

i

Ai

)

≤

∑

i

P (Ai)

The union of a bunch of events simply means “the event that at least one of these events happens”,

and obviously cannot exceed the sum of the individual probabilities of the events, because that is

the probability that they all happen in the extreme case that they are all independent. It might be

smaller if some of the events are overlapping. For example, say that A1 is the event that the Blue

Jays win, and P (A1) = 0.4, and say that P2 is the event that it rains, and P (A2) = 0.25. The

probability that at least one of A1 and A2 happens (either it rains or they win) cannot be greater than

P (A1) +P (A2) = 0.4 + 0.25 = 0.65. It could be smaller though (for example, if it only rains when the

Blue Jays win).

• A Useful Limit. Oftentimes you want to reason about the probability that a bunch of events don’t

happen. If the probability of one of the events happening can be expressed as 1/x, and there are x

independent events, then you can use:

lim

x→∞

(

1− 1

x

)x

=

1

e

1

CSCC46 Social and Information Networks Fall 2020 University of Toronto Scarborough

• Change of Base Formula. To change the base of a logarithm from α to β, use:

logα x =

logβ x

logβ α

Question 1: Signed Networks [25 pts]

1.1 [10 pts] In this question, we will analyze a simple generative model of signed networks to see if balance

occurs randomly. Consider the following simple model for constructing random signed networks, which

we’ll call the G+ model. Start with a complete graph on n nodes. For each edge e mark its sign as

positive with probability p (and thus negative with probability 1− p). All edges are undirected.

Let GB denote the event that a graph G is balanced. In this question, we’ll show that P (GB) → 0 as

n→∞ for graphs generated according to the G+ model. Assume that p = 1/8.

(a) [2 pts] Let T be a maximum set of disjoint-edge triangles in G. A “disjoint-edge” set of triangles

is one in which every edge is in exactly one triangle. Give a simple lower bound for |T |, the number

of triangles that don’t share any edges in G (the bound should be an increasing function of n).

(b) [2 pts] For any triangle in G, what is the probability that it is balanced?

(c) [4 pts] Using the simple lower bound from part (a), give an upper bound on the probability that

all of the triangles in T are balanced. Show that this probability approaches 0 as n→∞.

(d) [2 pts] Explain why the last part implies that P (GB)→ 0 as n→∞.

1.2 [5 pts] If balanced signed networks don’t show up by chance, as we showed in the previous question,

how do they arise? One class of mechanisms that researchers have proposed and studied are dynamic

processes, in which signed networks can evolve over time to become more balanced. The following

describes a very simple example of such a dynamic process:

I Pick a triad at random.

II If it’s balanced, do nothing.

III Otherwise, arbitrarily choose one of the edges and flip its sign so that the triad becomes balanced.

Consider the following claim: in this process, the number of balanced triads can never decrease. Is this

true? If so, give a proof, otherwise give a counterexample.

1.3 (a) [5 pts] One way signed networks can evolve over time is if new nodes join the network and create

new signed edges to nodes already in the network. Consider the simple network shown below. Is it

possible to add a node D such that it forms signed edges with all existing nodes (A, B, and C), but

isn’t itself part of any unbalanced triangles? Justify your answer.

A

B C

+

+

−

(b) [5 pts] Using your answer to the previous sub-problem, consider the following question. Take any

complete signed network, on any number of nodes, that is unbalanced. When (if ever) is it possible

for a new node X able to join the network and form edges to all existing nodes in such a way that it

does not become involved in any unbalanced triangles? If it’s possible, give an example. If it’s not,

give an argument explaining why.

2

CSCC46 Social and Information Networks Fall 2020 University of Toronto Scarborough

Question 2: Decentralized Search [50 pts]

In class, we saw a decentralized search algorithm based on “geography” that seeks a path between two nodes

on a grid by successively taking the edge towards the node closest to the destination.

Here we will examine an example of a decentralized search algorithm on a network where the edges are cre-

ated according to an underlying hierarchical tree structure. In particular, the nodes of our network will be

defined as the leaves of a tree, and the edge probabilities between two nodes will depend on their proximity

in this underlying tree structure. The tree may, for instance, be interpreted as representing the hierarchical

organization of a university where one is more likely to have friends inside the same department, a bit less

likely in the same school, and the least likely across schools.

Let us organize students at U of T into a tree hierarchy, where the root is University of Toronto and the

second level contains the different schools (engineering, arts and sciences, etc.). The third level represents

the departments and the final level (i.e., the leaves) are the U of T students. Fatima, a student from the

computer science department, wants to hang out with Max, who is in sociology. If Fatima does not know

Max, she could ask a friend in the sociology department to introduce them. If Fatima does not know anybody

in the sociology department, she may seek a friend in the U of T humanities school instead. In general, she

will try to find a friend who is “close” to Max in the tree.

One important thing to keep in mind: In this problem, the network nodes are only the leaf nodes in

the tree. Other nodes in the tree are virtual and only there to determine the edge creation probabilities

between the nodes of the network. So there are two networks: one is the observed network (i.e., “edges

between students”) and the other is the underlying tree structure that is used to generate the edges in the

observed network (“the hierarchy of U of T”).

Figure 1: Illustration of the graph in Question 2. Black nodes and edges are used to illustrate the hierarchy

and structure, but are not part of our network. Red nodes (leaf nodes) and red edges are the ones in our

network. The lowest common ancestor of s and t is the root of the tree. The decentralized search proceeds

as follows. Denote the starting node by s and the destination by t. At each step, the algorithm looks at

the neighbors of the current node s and moves to the one “closest” to t, that is, the algorithm moves to the

node with the lowest common ancestor with t. In this graph, from s we move to u.

2.1 This part covers some basic facts of the setting of the hierarchical model and defines the notion of

tree-based “distance” between the nodes.

Consider a complete, perfectly balanced b-ary tree T (each non-leaf node has b children and b ≥ 2), and

a network whose nodes are the leaves of T (the red nodes in Figure 1). Let the number of network nodes

(equivalently, the number of leaves in the tree) be N and let h(T ) denote the height of T (see Figure 1

for an example). Recall that a tree with one node has a height of zero.

3

CSCC46 Social and Information Networks Fall 2020 University of Toronto Scarborough

Note: When answering questions in this section, feel free to cite well-known properties of trees (e.g.,

number of nodes in a complete binary tree of a certain height), but please provide evidence of reasoning

as well. In other words, we don’t expect you to prove basic tree properties by induction; just provide

some sound reasoning.

(a) (2 points) Write h(T ) in terms of N .

(b) (3 points) Next we want to define the notion of “tree distance.” The intuition we want to capture

is that students that share the same department are closer than, for example, students who only

share the same school. For instance, in the tree in Figure 1 nodes u and t are “closer” than nodes u

and s. We formalize the notion of “distance” as follows.

Given two network nodes (leaf nodes) v and w, let L(v, w) denote the subtree of T rooted at the

lowest common ancestor of v and w, and h(v, w) denote its height (that is, h(L(v, w))). In Figure 1,

L(u, t) is the tree in the circle and h(u, t) = 2. Note that we can think of h(v, w) as a “distance”

between nodes v and w.

For a given node v, what is the maximum possible value of h(v, w)?

(c) (5 points) Given a value d and a network node v, show that there are bd − bd−1 nodes satisfying

h(v, w) = d.

2.2 This part helps you design a decentralized search algorithm in the network.

We will generate a random network on the leaf nodes in a way that models the observation that a node

is more likely to know “close” nodes than “distant” nodes according to our university organizational

hierarchy captured by the tree T . For a node v, we define a probability distribution of node v creating

an edge to any other node w:

pv(w) =

1

Z

b−h(v,w)

where Z =

∑

w 6=v b

−h(v,w) is a normalizing constant. By symmetry, all nodes v have the same normalizing

constant. Next, we set some parameter k and ensure that every node v has exactly k outgoing edges.

We do this with the following procedure. For each node v, we repeatedly sample a random node w

according to pv and create edge (v, w) in the network. We continue this until v has exactly k neighbors.

Equivalently, after we add an edge from v to w, we can set pv(w) to 0 and renormalize with a new Z to

ensure that

∑

w p(w) = 1. This results in a k-regular directed network.

(a) (7 points) Show that Z ≤ logbN . (Hint: use the results in parts 2.1(a) and 2.1(b), and group

nodes by their distance. For each distance d, you know exactly how many nodes are at distance d

and you have a lower bound for the probability of linking to them).

(b) (8 points) For a node v and the target t, let T ′ be the subtree of L(v, t) satisfying:

• T ′ is of height h(v, t)− 1,

• T ′ contains t,

• T ′ does not contain v.

For instance, in Figure 1, T ′ of L(s, t) is the tree in the circle. Let us consider an edge e from v to a

random node u sampled from pv. We say that e points to T

′ if u is one of the leaf nodes of T ′. Show

that the probability of e pointing to T ′ is no less than 1b logbN . (Hint: Note that all of the nodes in

T ′ are the same distance away from v, by our notion of tree distance that we defined in 2.1(b). How

many nodes are in T ′?)

2.3 (15 points) Let the out-degree k for each node be c · (logbN)2, where c and b are constants. Show that

when N grows very large, the probability that v has no edge pointing to T ′ is asymptotically no more

than N−θ, where θ is a positive constant which you need to compute. (Hints: Use the result in part

2.2(b) and recall that each of the k edges is independently created. Also, use limx→∞(1 − 1x )x = 1e .)

4

CSCC46 Social and Information Networks Fall 2020 University of Toronto Scarborough

Argue why the above result indicates that for any node v, we can, with high probability, find an edge to

a (leaf) node u satisfying h(u, t) < h(v, t).

2.4 (10 points) Show that starting from any (leaf) node s, within O(logbN) steps, we can reach any (leaf)

node t. You do not need to prove it in a strict probabilistic argument. You can just assume that for any

(leaf) node v, you can always get to a (leaf) node u satisfying h(u, t) < h(v, t) and argue why you can

reach t in O(logbN) steps.

Power Laws [25 pts]

3.1 [10 pts] The main summary statistics of distributions are called moments. For example, the mean

is also known as the first moment and the variance is also known as the second moment. In Lecture

6, we calculated the mean of a power law distribution. In this question, calculate the skewness of a

power law distribution, which is also known as the third moment. That is, calculate

∫∞

xmin

x3p(x)dx,

where

p(x) =

α− 1

xmin

( x

xmin

)−α

3.2 [15 pts] As we learned in class, the power law can be a great fit for the heavy-tailed data we en-

counter in real-world networks. But one problem we have to overcome is: what parameters are the

best fit? The power law is characterized by the minimum x-value xmin and the slope α. In this

question, we’ll learn how to estimate α from data.

Say you have a dataset {xi | i ∈ {1, . . . , n}} of n numbers, and you suspect these numbers come from

a power law distribution and want to find the best fit α. The strategy we’re going to use to estimate

α is called the maximum likelihood approach. We’re going to compute the log-likelihood of the

data given a power law model, then calculate which value of α maximizes this log-likelihood (we

take the log of the likelihood to simplify the math).

(a) [5 pts] Let L(α) = ln (∏ni p(xi)) be the log-likelihood of the data as a function of α. Plug in the

definition of a power law for p(xi) (shown above in Question 1.1) and simplify the expression

for L(α).

(b) [10 pts] Now take the derivative of L(α) with respect to α and set it to zero:

dL(α)

dα

= 0

This is now a simple single-variable calculus problem. Solve this equation to get the value of α

that maximizes the log-likelihood of the data. That is the value of α that fits the data best.

5

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写
- archi代写
- Propositional Logic代写
- 国际财务管理代写
- 高宏代写
- 模型代写
- 润色代写
- 营养学论文代写
- 热力学代写
- Acct代写
- Data Synthesis代写