CE634 Assignment-2
Derive Community Structures from Taxi Flow Network
1. Introduction
In assignment 1, you have performed an exploratory data analysis to derive meaningful statistics of the taxi
GPS dataset. Some of the questions listed in assignment 1 allow us to generate insights into the spatial or
temporal distribution of travel demand in NYC. However, none of the questions require us to couple trip
origins and destinations together. In other words, the interactions among different locations in the study
area remain unexplored.
In this assignment, you will be asked to perform a network analysis, namely community detection, to
uncover the hidden structures in the flow network derived from the taxi GPS dataset. According to
Wikipedia:
“In the study of complex networks, a network is said to have community structure if the nodes of the
network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes
is densely connected internally. In the particular case of non-overlapping community finding, this
implies that the network divides naturally into groups of nodes with dense connections internally and
sparser connections between groups. But overlapping communities are also allowed. The more
general definition is based on the principle that pairs of nodes are more likely to be connected if they
are both members of the same community(ies), and less likely to be connected if they do not share
communities. A related but different problem is community search, here the goal is to find a
community that a certain vertex belongs to.”
Thus, the community detection algorithm(s) can be applied to our taxi GPS dataset to derive community
structures such that the taxi flows (e.g., origin-destination trips) within the communities are denser while
CE634留学生作业代做、代写Flow Network作业
inter-community flows are sparser. The results could generate insights into the spatial interactions among
different locations in the city.
2. About Community Detection
2.1. Derive taxi flow network from the GPS dataset
The taxi GPS dataset makes it possible for us to derive the origin-destination (OD) trips that contain rich
information of the location interactions in the Manhattan area. Usually, a community detection algorithm
is performed over a network, with the nodes representing particular entities, and the links (and weights)
denoting the interactions among these nodes.
In this assignment, you will first derive a flow network, in which the nodes are represented by various
locations (or places) in the study area, where the links between the nodes are measured as the total amount
of taxi trips between the corresponding locations.
Instead of representing the nodes using road intersections, we use taxi zones in this analysis to represent
different places (e.g., nodes) in the flow network. The reason is that using taxi zones will significantly
reduce the number of nodes and edges in the network, which makes the computation time (of the community
detection) more reasonable.
2
To accomplish this task, you are provided with another file:
− intersection_to_zone
This file maps each road intersection onto a particular taxi zone in Manhattan. Two columns, namely
inter_id and zone_id, denote the id of the road intersection and the taxi zone, respectively.
What you need to do is to analyze the original taxi GPS dataset, derive the OD trips at the level of road
intersections, and transform the network onto taxi zones. To make it clear, the final network used for the
community detection consists of 63 nodes that denote the taxi zones in Manhattan, with the weight of the
edges as the amount of taxi trips between the zones.
2.2. Perform the community detection algorithm
There are many community detection algorithms (https://en.wikipedia.org/wiki/Community_structure),
with their own pros and cons. In this assignment, you are asked to apply the algorithm proposed by Blondel
et al., (2008). The implementation is described in details in this article.
3
However, to facilitate the analysis, you are encouraged to use existing libraries & APIs. In particular, igraph
(http://igraph.org/), which is a collection of network analysis tools, allows you to perform this algorithm
through a couple of programming languages such as Python, R, and C. The python API for this algorithm
can be found at http://igraph.org/python/doc/igraph.Graph-class.html#community_multilevel.
A few things for your attention:
• You first have to figure out how to install the package (http://igraph.org/python/);
• And then follow the tutorial and learn how to establish a graph, i.e., network
(http://igraph.org/python/doc/tutorial/tutorial.html);
• Then, apply the so called multilevel community detection algorithm proposed by Blondel et al.
3. Tasks
(1) Derive the flow network at the level of taxi zones.
(2) Understand the multilevel community detection algorithm and perform it over the flow network. The
output of your analysis would be a collection of clusters or communities, with each community including
a list of taxi zones with frequent interactions.
(3) You are asked to form the flow network during the following time periods, and derive the corresponding
communities:
• Using taxi trips occurred during 07:00 – 09:00 throughout the whole year
• And those during 16:00 – 18:00 throughout the whole year
• Using taxi trips of each of the twelve months.
4. What to Submit
− A word document or pdf file with 1-2 paragraphs of your understanding of the multilevel
community detection algorithm and the key concepts (e.g., modularity).
− The results of the communities based on (3), i.e., results for 14 different scenarios.
− The submission due date is November 25
th, 2019.
References
Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in
large networks. Journal of statistical mechanics: theory and experiment, 2008(10), P10008.

 

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 

微信：codehelp