The purpose of these courses are to introduce students to research techniques in computer engineering and science. Over the years, undergraduate students have participated in many of our projects within this course, leading to useful components of larger software systems and many new methods published in leading journals.
Refer to course pages CS390 and CS490 for prerequisites and conditions.
CiSE (Circular Spring Embedder) is an algorithm for automatic layout of clustered graphs using a circular style. The algorithm tries to determine optimal location and orientation of individual clusters intrinsically within a modified spring embedder. Heuristics such as reversal of the order of nodes in a cluster and swap of neighboring node pairs in the same cluster are employed intermittently to further relax the spring embedder system, resulting in reduced inter-cluster edge crossings. Unlike other algorithms generating circular drawings, CiSE does not require the quotient graph to be acyclic, nor does it sacrifice the edge crossing number of individual clusters to improve respective positioning of the clusters. Moreover, it reduces the total area required by a cluster by using the space inside the associated circle.
Cytoscape.js is a graph library for effective visualization and analysis of networks.
This project aims to implement CiSE as a Cytoscape.js extension and to improve it with respect to commonly accepted graph layout criteria such as number of edge crossings and total area.
CoSE (Compound Spring Embedder) is a layout algorithm for undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints.
Cytoscape.js is a graph library for effective visualization and analysis of networks. Existing implementations of CoSE are available, including one as a Cytoscape.js extension. Even though CoSE is fairly fast as a spring embedder algorithm and works well with small to medium sized graphs, it fails to complete within acceptable time when used as part of an interactive visualization tool for large sized graphs.
This project aims to speed up the algorithm by potentially using techniques such as:
Disconnected graphs occur rather frequently in real life applications either during the construction of a graph interactively or because of the nature of the application. Most graph layout algorithms assume a graph to be connected and try to minimize the area needed for the resulting drawing. No matter how effective such an algorithm is, the space wasted overall could be arbitrarily large if the relative locations of disconnected objects of a graph are chosen by a naive, inefficient method. Another key parameter here is the aspect ratio of the region (e.g., a window) within which the graph is to be displayed. When displaying a graph, the larger the wasted space is, the less visible objects will be, making the visualization process more difficult. Thus, a disconnected graph layout algorithm must strive for a packing of disconnected objects which respects the aspect ratio of the region in which it is to be displayed.
Cytoscape.js is a graph library for effective visualization and analysis of networks. The aim of this project is to implement a polyomino based approach developed in the past for disconnected graph layout as a Cytoscape.js extension, and improve the algorithm in certain ways. In particular, we need a heuristic to determine the size of the grid used in forming polyominoes based on the input graph.
Most network visualization based analysis tools have similar requirements. These include ability to
Cytoscape.js is a graph library for effective visualization and analysis of networks. This project aims to design and implement a designer tool that takes the schema of a graph (could be defined using rdf) from an arbitrary domain and generates the necessary style sheets / code for a Cytoscape.js based visualization tool that supports above capabilities.
The cBioPortal for Cancer Genomics provides visualization, analysis and download of large-scale cancer genomics data sets. A tool named PathwayMapper was previously developed with the motivation of creating a platform providing more intuitive template pathway diagrams with rich data decoration and analysis with access to data in cBioPortal. PathwayMapper can also be used as a valuable tool for constructing pathways from scratch.
PathwayMapper is based on Cytoscape.js, which is a graph library for effective visualization and analysis of networks.
This project aims to integrate PathwayMapper into cBioPortal as an alternative to the cBioPortal's current network view. Ways to instantiate PathwayMapper from existing cBioPortal pages need to be designed.
Recently, detection of fraud is an increasingly important and challenging task. Since we maintain more and more personal data online, potential losses due to fraud increased to billions of dollars. Use of advanced querying of databases and visualization, especially of CDR, is critical in detecting fraud.
Cytoscape.js is a graph library for effective visualization and analysis of networks. This project aims to study fraud detection methods and develop a Cytoscape.js based tool for detecting fraud in CDR data stored in graph databases thorough advanced querying and visualization.
Often times huge amounts of data available for intelligence and security tasks is not very useful since they are mostly kept as tables in relational databases. Recent rise of graph based databases not only facilitate application of advanced querying in such large databases and raising alerts as needed but also facilitate mechanisms to effectively visualize the indirect connections in the data in detecting anomalies and security problems.
Cytoscape.js is a graph library for effective visualization and analysis of networks. This project aims to study intelligence and security analysis through advanced querying and network visualization.