Visual Clustering of Social Network (40%)
32146 DVVA Assignment 3
Social networks are ubiquitous. A fundamental problem related to these networks is the discovery of clusters or communities. Intuitively, a cluster is a collection of individuals with dense friendship patterns internally and sparse friendships externally.
The discovery of close-knit clusters in these networks is of fundamental and practical interest and the one of major focused problems in AI and Data Mining. There are many reasons to seek tightly-knit communities in networks, for instance, target marketing schemes can be designed based on clusters, and it has been claimed that terrorist cells can be identified.
This assignment gives students two options with different requirements based on student’s disciplinary background, personal preference and existing experience. This is to satisfy the students who are not major in IT and Mathematics (Algorithms).
Option One: (group work):
A group of two students are required to work together to analyze an organization’s email network (a type of social networks) through the data clustering and a clustered graph visualization.
Task 1: through data clustering, we can identify abnormal (implicit) network patterns that against the hierarchical structure of the organization,
Task 2: through a clustered graph visualization, we can visually read and quickly understand the data clustering output, including the abnormal network patterns.
Option Two: (individual work):
An individual student is required to visualize an organization’s email network (a type of social networks) through graph visualization and clustered graph visualization.
Task 1: using graph visualization to visualize attributed email network,
Task 2: using clustered graph visualization to visualize a given clustered email network that enables readers to quickly understand the data clustering output.
1|Page
The weight of this assignment is 40%.
Specification:
The following Figure shows the organization structure of TACME, sourced from http://www.tacme.com/corporate_structure.html
A list of staff’s ID, Name and Position in TACME
ID
Name
Position
0
James
1 Director
Director
David
2
George
CEO
3
5
7
9
11
13
15
17
Business Development Manager
Business Support Manager
Business Control Manager
Sales Department Leader
Product Department Leader
Marketing Department Leader
Project Office Leader
Professional Service Leader
QA Leader
Design Office Leader
Technical Support Office Leader
Software Development Leader
Legal Office Leader
Finance Office Leader
HR Office Leader
Ronald
4
John
Richard
6
Daniel
Kenneth
8
Anthony
Robert
10
Charles
Paul
12
Mark
Kevin
14
Edward
Joseph
16
Michael
Jason
2|Page
The Email communication detail in a particular month is shown below: ID Emails per month Weight ID
0612
2 25 2 3
2 53 3 5
3 213 5 7
4 345 6 9
4 212 5 11
4 156 4 13
5 300 5 15
5 256 5 17
6 145 4 8
9 34 2 10
9 546 7 12
9 145 4 14
10 222 5 12
10 56 3 14
11 112 4 13
15 88 3 16
16 238 5 17
16 15 2 6
0511
1512
2 36 2 4
3 150 4 6
3 298 5 8
4 123 4 10
4 453 7 12
4 278 5 14
5 78 3 16
6 78 3 7
7 139 4 8
9 134 4 11
9 23 2 13
10 256 5 11
10 190 4 13
11 78 3 12
12 98 3 14
15 128 4 17
17 5 1 7
16 23 2 7
3|Page
16 8
9
16 11
13
16 14
54
3
16
18
2
23
2
16
41
2
Weight description: Quantity
11 – 50 101 – 200 301 – 400
General Requirement:
Weight
2
3
4
5
6
13
2
16
27
2
10
<10
1
51 – 100
201 – 300
> 401
7
Option One: (group work)
Students are required:
1) To draw (visualize) the original email network on the paper (or screen) with the satisfaction of the following Aesthetics Rules: a) Symmetrical Display, b) Minimization of Edge-Crossings and c) Maximization of Angular Resolution. In addition, since each edge e in the graph is associated with a weight w(e), you need to map the w(e) to a graphical attribute, such as color, types of line, size or shapes, to enhance the readbility of the weight
2) To cluster this email network (or graph) into clustered structures by using Markov Clustering Algorithm. You need to produce two clustered structures 1) with the weight w(e), 2) without the weight w(e) .
3) Discuss the findings. If there is one (or more) abnormal network pattern(s) found, you need to describe them in details.
4) To draw (visualize) these two clustered graphs (one with w(e), another without w(e) ) on the paper (or screen). Using geometric rectangles (or circles) to bound clusters in the drawing. Make sure that these regions are not overlapped. In addition, these drawings shall also satisfy the general graph drawingaesthetics.
4|Page
Option Two: (individual work)
Student is required:
1) To draw (visualize) the original email network on the paper (or screen) with the satisfaction of the following Aesthetics Rules: a) Symmetrical Display, b) Minimization of Edge-Crossings and c) Maximization of Angular Resolution. In addition, since each edge e in the graph is associated with a weight w(e), you need to map the w(e) to a graphical attribute, such as color, types of line, size or shapes, to enhance the readability of the weight
2) To draw (visualize) a given clustering of the above email graph, that is: {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}, {12, 13, 14}, {15, 16, 17} on the paper (or screen). Using geometric rectangles (or circles) to bound clusters in the drawing. Make sure that these regions are not overlapped. In addition, these drawings shall also satisfy the general graph drawing aesthetics, including a) Symmetrical Display, b) Minimization of Edge-Crossings and c) Maximization of Angular Resolution.
5|Page