During my time in research, my main research area was social network analysis, especially dynamic networks. Yet, I have a broad range of research interests. Various topics of social and wireless networks (either theoretical or experimental) and data center networks are among my research interests and experience, including:
- Social network analysis
- Dynamic graph(network) algorithms
- Spatiotemporal analysis
- Multi-hop wireless ad-hoc/mesh networks
- Resource allocation and scheduling
Incremental Algorithms for Dynamic Networks
This work is my Ph.D. dissertation.
The increasing availability of online resources such as digital libraries and social networking websites has led to an upsurge of interest in the analysis of social networks. To date, a wealth of social cent rality measures have been designed for determining the importance of nodes in a social network from different aspects. A significant number of social centrality metrics depend on the shortest paths in the network, usually requiring solving the all-pairs shortest path problem. However, most of these metrics were designed for static snapshots of 20-30 node networks. Computing centrality metrics in dynamically changing, large networks is almost unfeasibly costly, especially if it involves repeatedly calculating centralities from scratch for each incremental change. My thesis proposes incremental algorithms for the two of the most popular shortest- path based social centrality metrics (e.g. closeness centrality and betweenness centrality) to avoid computations from scratch by performing early-pruning and achieving substantial performance improvements in dynamically changing networks. It explores the computational time savings and the memory requirements as the realistic social networks being analyzed scale to very large sizes. The key idea is to start with the old output of the algorithm and to modify/update only the affected values such that the changes in the network (e.g. edge/node insertions/deletions/modifications) are reflected in the centrality values as well. The approximate versions of incremental closeness and betweenness centralities through k-hop bounded computations are also designed where the shortest paths included in the computations should be less than or equal to k; forcing the centrality computations to remain within a k-hop subgraph of a node instead of the entire graph. The performance results obtained via experiments on a wide variety of synthetic and real-life dynamic networks suggest substantial improvements over the state of the art.
This work is my Ph.D. dissertation.
The increasing availability of online resources such as digital libraries and social networking websites has led to an upsurge of interest in the analysis of social networks. To date, a wealth of social cent rality measures have been designed for determining the importance of nodes in a social network from different aspects. A significant number of social centrality metrics depend on the shortest paths in the network, usually requiring solving the all-pairs shortest path problem. However, most of these metrics were designed for static snapshots of 20-30 node networks. Computing centrality metrics in dynamically changing, large networks is almost unfeasibly costly, especially if it involves repeatedly calculating centralities from scratch for each incremental change. My thesis proposes incremental algorithms for the two of the most popular shortest- path based social centrality metrics (e.g. closeness centrality and betweenness centrality) to avoid computations from scratch by performing early-pruning and achieving substantial performance improvements in dynamically changing networks. It explores the computational time savings and the memory requirements as the realistic social networks being analyzed scale to very large sizes. The key idea is to start with the old output of the algorithm and to modify/update only the affected values such that the changes in the network (e.g. edge/node insertions/deletions/modifications) are reflected in the centrality values as well. The approximate versions of incremental closeness and betweenness centralities through k-hop bounded computations are also designed where the shortest paths included in the computations should be less than or equal to k; forcing the centrality computations to remain within a k-hop subgraph of a node instead of the entire graph. The performance results obtained via experiments on a wide variety of synthetic and real-life dynamic networks suggest substantial improvements over the state of the art.
Social Prism: Visual Summaries of Topical Clusters in Twitter Streams
As a huge amount of tweets become available online, it has become an opportunity and a challenge to extract useful information from tweets for various purposes. We propose a novel way to extract topical structure from a large set of tweets and generate a usable summarization along with related topically popular keywords. We build a research prototype, Social Prism that collects the tweets, processes them for text analysis, identifies clusters of relevant words, and generates visual summaries. We also perform a user study and the result suggests that users are able to detect relevant information and infer relationships between keywords better with our summarization method than they do with the commonly used word cloud visualizations.
I worked on this project under the supervision of Prof. Bongwon Suh during my internship at Adobe Research.
As a huge amount of tweets become available online, it has become an opportunity and a challenge to extract useful information from tweets for various purposes. We propose a novel way to extract topical structure from a large set of tweets and generate a usable summarization along with related topically popular keywords. We build a research prototype, Social Prism that collects the tweets, processes them for text analysis, identifies clusters of relevant words, and generates visual summaries. We also perform a user study and the result suggests that users are able to detect relevant information and infer relationships between keywords better with our summarization method than they do with the commonly used word cloud visualizations.
I worked on this project under the supervision of Prof. Bongwon Suh during my internship at Adobe Research.
Trends in Scientific Networks
The growing of availability of electronic resources over the Internet enables rapid dissemination of the ideas and changes in the trends and the interaction patterns. In this work, we focus on dynamic, evolving social networks which exhibit numerous features that are also of interest to many researchers in non-social fields such as statistical physics, biology, applied mathematics, and computer science. We investigate how a specific research area (high-energy physics) changes over time, by building complex, interlinked citation, publication, and co-publication networks that evolve and expand constantly through the emergence of new papers and authors. Following an interdisciplinary approach, we perform a wide-ranging analysis of the high-energy physics dataset using techniques such as social networks centrality analysis, topological analysis, investigation of power law characteristics, time series analysis of publication and collaboration frequencies, as well as spatiotemporal analysis to discuss relationships among involved countries.
The growing of availability of electronic resources over the Internet enables rapid dissemination of the ideas and changes in the trends and the interaction patterns. In this work, we focus on dynamic, evolving social networks which exhibit numerous features that are also of interest to many researchers in non-social fields such as statistical physics, biology, applied mathematics, and computer science. We investigate how a specific research area (high-energy physics) changes over time, by building complex, interlinked citation, publication, and co-publication networks that evolve and expand constantly through the emergence of new papers and authors. Following an interdisciplinary approach, we perform a wide-ranging analysis of the high-energy physics dataset using techniques such as social networks centrality analysis, topological analysis, investigation of power law characteristics, time series analysis of publication and collaboration frequencies, as well as spatiotemporal analysis to discuss relationships among involved countries.
What if Wireless Routers were Social?
Wireless Mesh Networks (WMNs) consist of radio nodes organized in a mesh topology for serving wireless mesh clients to communicate with one another or to connect to the Internet. Nodes in a mesh network can communicate with each other either directly or through one or more intermediate nodes, similar to social networks. WMNs share many common properties with social networks. We first identify the differences and similarities between social networks and WMNs and then use metrics that are typically used for social network analysis (SNA) to assess real WMNs. Analyzing real WMN data collected from the UCSB MeshNet and MIT Roofnet testbeds reveals that using SNA metrics are helpful in designing WMNs with better performance. We demonstrate the validity of our conclusions and this new approach by focusing on two sample applications of social networks: network reliability assessment and channel access scheduling.
Wireless Mesh Networks (WMNs) consist of radio nodes organized in a mesh topology for serving wireless mesh clients to communicate with one another or to connect to the Internet. Nodes in a mesh network can communicate with each other either directly or through one or more intermediate nodes, similar to social networks. WMNs share many common properties with social networks. We first identify the differences and similarities between social networks and WMNs and then use metrics that are typically used for social network analysis (SNA) to assess real WMNs. Analyzing real WMN data collected from the UCSB MeshNet and MIT Roofnet testbeds reveals that using SNA metrics are helpful in designing WMNs with better performance. We demonstrate the validity of our conclusions and this new approach by focusing on two sample applications of social networks: network reliability assessment and channel access scheduling.
