General Information

Name: Jiajun Chen
Email: ab792638826@gmail.com
Office: Virtual
Education: Stony Brook University
Partner Moriah Walker
Mentor: Dr.James Abello, Haoyang Zhang
Project: Graph Cities Experimentation

About My Project

The main goal for this project is to create a catalog of subgraph patterns and implement a pattern-recognition algorithms to generate a "human-interpretable story" that can be extracted from this massive dataset.

Weekly Summary

Week 1

For the first week of the REU program, it is beginned with an orientation with DIMACS REU, followed by the first group meeting with my team: Moriah Walker, Dr. James Abello and Haoyang Zhang. Professor introduced the project called "Graph Cities Experimentation" I will be working on during this program, as well as some supplemental knowledge for this project. All in all, I am very looking forward to the program.

Week 2

This week started with brief presentations on the research topic from every participant in DIMACS REU program, I had present my research as well, called Graph Cities Experiemntations with my partner, Moriah Walker. After that, we had a weekly group meeting with Dr. Abello and Haoyang Zhang. We first talk about what can be improved in future presentations. And then discuss some interesting patterns in graph. I am able to get a general idea of what we are going to focus on by the end of this week. Here, shoutout to Dr. Abello and Haoyang Zhang.

Week 3

During the weekly meeting, we had discussed about some interested graph patterns found in graph city. Common patterns include tree,star,clique. But our discover doesn't limit to these patterns. Also, we are trying to formulate a conjecture based on our finding, and comes up with a mathematics proof of it.

Week 4

During this week, we have found some interesting patterns on graph strata. My mentor, Dr. James Abello have introduced an method to investigate and describe patterns that can be applied to a generalized clique. We have also continued to discuss the conjecture we have proposed. Hao Yang finds an counterexample of it and we need to proper formulated it again so that it can be true.

Week 5

During this week, we continue to discuss some of the interesting patterns by unleash its internal representation and meaning. For one of the patterns I found, as Professor suggested, some of the nodes might have a very similiar representation because of the shape of the whole graph. And I will verify this in next week. This is quite interesting because it may reveals how the shape of patterns indicates the close relationship between vertices in graph.

Week 6

This week, we are continued to work on finding new patterns. Dr. Abello has taught us another way to describe unknown patterns using the the idea of "starting from min degree vertices". This is the ultimate tool that can be used to describe all patterns. However, we also want to categorize those patterns we haven't seen before. So far, we have "star","k-tree","clique" patterns and we want to categorize more patterns. After collecting enough patterns, we will start to look at its semantics behind these patterns.

Week 7

This week, I had been putting my effort on finding the patterns on "Movies" graph dataset. In this week meeting, Prof James Abello suggests us to look at the semantics of these graphes so that it can be written in our final report. He also walks through how does a story be generated based on the name of each vertex. And he also stressed that this stories doesn't have to make sense sometimes.

Week 8

I had been working on the presentation slides and final report for my REU experience during this week.

Week 9

This week is the last week of the REU experience, I had present my work scheduled for Friday and it is a great experience overall. Shoutout to My mentor: Prof James Abello and Haoyang for all their guidance on our final presentation. And also my partner: Moriah Walker.

-->

References & Links

  1. Abello, James & Mawhirter, Daniel & Sun, Kevin. (2019). Taming a Graph Hairball: Local Exploration in a Global Context. 10.1007/978-3-030-06222-4_10.

    Abello, J., Quelroy, F.: Network decompositions into fixed points of degree peeling. Social Networks Analysis and Mining pp. 4–19 (2014).

    Abello, J., & Nakhimovich, D. (2020). Graph waves. CEUR Workshop Proceedings, 2578.

    Abello, J., Hohman, F., Bezzam, V., & Chau, D. H. (2019). AtlaS: Local graph exploration in a global context. 165-176. Paper presented at 24th ACM International Conference on Intelligent User Interfaces, IUI 2019, Marina del Ray, United States.

    ualberta.ca. (n.d.). Unpacking World Folk-literature: Thompson’s Motif Index, ATU’s Tale Type Index, Propp’s Functions and Lévi-Strauss’s Structural Analysis for folk tales found around the world. Sites.Ualberta.Ca. Retrieved July 21, 2020, from https://sites.ualberta.ca/~urban/Projects/English/Motif_Index.htm

    Wikipedia contributors. (2020, June 7). Aarne–Thompson–Uther Index. In Wikipedia, The Free Encyclopedia. Retrieved 09:20, July 21, 2020, from https://en.wikipedia.org/w/index.php?title=Aarne%E2%80%93Thompson%E2%80%93Uther_Index&oldid=961220406

Here is the REU website: