Award Date

5-1-2016

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Justin Zhan

Second Committee Member

Laxmi Gewali

Third Committee Member

Fatma Nasoz

Fourth Committee Member

Darren Liu

Number of Pages

54

Abstract

Graphs and Networks have been the most researched topics with applications ranging from theoretical to practical fields, such as social media, genetics, and education. In many competitive environments, the most productive activities may be interacting with high-profile people, reading a much-cited article, or researching a wide range of fields such as the study on highly connected proteins. This thesis proposes two methods to deal with top-K nodes identification: centrality-based and activity-based methods for identifying top-K nodes. The first method is based on the topological structure of the network and uses the centrality measure called Katz Centrality; a path based ranking measure that calculates the local influence of a node as well as its global influence. It starts by filtering out the top-K nodes from a pool of network data using Katz Centrality. By providing a means to filter out unnecessary nodes based on their centrality values, one can focus more on the most important nodes. The proposed method was applied to various network data and the results showed how different parameter values lead to different numbers of top-K nodes. The second method incorporates the theory of heat diffusion. Each node in the network can act as the source of heat. The amount of heat diffused or received by the node depends on the number of activities it performs. There are two types of activities: Interactive and Non-Interactive. Interactive activities could be likes, comments, and shares whereas posting a status, tweets or pictures could be the examples of non-interactive activities. We applied these proposed methods on Instagram network data and compared the results with the other similar algorithms. The experiment results showed that our activity-based approach is much faster and accurate than the existing methods.

Images referenced in this thesis are included in the supplementary files.

Keywords

Big Network; Centrality; Diffusion; Influential; Social Network; Top-K nodes

Disciplines

Computer Sciences

Language

English

Comments

Additional files available for download: ZIP file containing PNG, EPS, and JPEG image files.

Images referenced in this thesis are included in the supplementary files.

Images.zip (950 kB)
Supplementary files


Share

COinS