Theory and Algorithms Commons^™

Fake News Analysis And Graph Classification On A Covid-19 Twitter Dataset, Kriti Gupta

Master's Projects

Earlier researches have showed that the spread of fake news through social media can have a huge impact to society and also to individuals in an extremely negative way. In this work we aim to study the spread of fake news compared to real news in a social network. We do that by performing classical social network analysis to discover various characteristics, and formulate the problem as a binary classification, where we have graphs modeling the spread of fake and real news. For our experiments we rely on how news are propagated through a popular social media services such as …

Higher-Order Link Prediction Using Graph Embeddings, Neeraj Chavan

Master's Projects

Link prediction is an emerging field that predicts if two nodes in a network are likely to be connected or not in the near future. Networks model real-world systems using pairwise interactions of nodes. However, many of these interactions may involve more than two nodes or entities simultaneously. For example, social interactions often occur in groups of people, research collaborations are among more than two authors, and biological networks describe interactions of a group of proteins. An interaction that consists of more than two entities is called a higher-order structure. Predicting the occurrence of such higher-order structures helps us solve …

Rehearsal Scheduling Problem, Thuan Bao

Master's Projects

Scheduling is a common task that plays a crucial role in many industries such as manufacturing or servicing. In a competitive environment, effective scheduling is one of the key factors to reduce cost and increase productivity. Therefore, scheduling problems have been studied by many researchers over the past thirty years. Rehearsal scheduling problem (RSP) is similar to the popular resource-constrained project scheduling problem (RCPSP); however, it does not have activity precedence constraints and the resources’ availabilities are not fixed during processing time. RSP can be used to schedule rehearsal in theatre industry or to schedule group scheduling when each member …

Network Alignment In Heterogeneous Social Networks, Priyanka Kasbekar

Master's Projects

Online Social Networks (OSN) have numerous applications and an ever growing user base. This has led to users being a part of multiple social networks at the same time. Identifying a similar user from one social network on another social network will give in- formation about a user’s behavior on different platforms. It further helps in community detection and link prediction tasks. The process of identifying or aligning users in multiple networks is called Network Alignment. More the information we have about the nodes / users better the results of Network Alignment. Unlike other related work in this field that …

Online Local Communities, Mrudula Murali

Master's Projects

A community in a network is a group of nodes that are densely and closely connected to each other, get sparsely connected to the nodes outside the community. Finding communities in a large network helps solve many real-world problems. But detecting such communities in a complex network by focusing on the whole network is not feasible. Instead, we focus on finding communities around one or more seed node(s) of interest. Therefore, in this project, we find local communities. Moreover, we consider the online setting where the whole graph is unknown in the beginning and we get a stream of edges, …

Deep Learning On Graphs Using Graph Convolutional Networks, Saurabh Mithe

Master's Projects

Graphs are a powerful way to model network data with the objects as nodes and the relationship between the various objects as links. Such graphs contain a plethora of valuable information about the underlying data which can be extracted, analyzed, and visualized using Machine Learning (ML). The challenge to this task is that graphs are non-Euclidean structures which means that they cannot be directly used with ML techniques because ML techniques only work with Euclidean structures like grids or sequences. In order to overcome this challenge, the graph structure first needs to be encoded into an equivalent Euclidean representation in …

Community Detection In Social Networks, Ketki Kulkarni

Master's Projects

The rise of the Internet has brought people closer. The number of interactions between people across the globe has gone substantially up due to social awareness, the advancements of the technology, and digital interaction. Social networking sites have built societies, communities virtually. Often these societies are displayed as a network of nodes depicting people and edges depicting relationships, links. This is a good and e cient way to store, model and represent systems which have a complex and rich information. Towards that goal we need to nd e ective, quick methods to analyze social networks. One of the possible solution …

Influence Detection And Spread Estimation In Social Networks, Madhura Kaple

Master's Projects

A social network is an online platform, where people communicate and share information with each other. Popular social network features, which make them di erent from traditional communication platforms, are: following a user, re-tweeting a post, liking and commenting on a post etc. Many companies use various social networking platforms extensively as a medium for marketing their products. A xed amount of budget is alloted by the companies to maximize the positive in uence of their product. Every social network consists of a set of users (people) with connections between them. Each user has the potential to extend its in …

Using Probabilistic Graphical Models To Solve Np-Complete Puzzle Problems, Fengjiao Wu

Master's Projects

Probabilistic Graphical Models (PGMs) are commonly used in machine learning to solve problems stemming from medicine, meteorology, speech recognition, image processing, intelligent tutoring, gambling, games, and biology. PGMs are applicable for both directed graph and undirected graph. In this work, I focus on the undirected graphical model. The objective of this work is to study how PGMs can be applied to find solutions to two puzzle problems, sudoku and jigsaw puzzles. First, both puzzle problems are represented as undirected graphs, and then I map the relations of nodes to PGMs and Belief Propagation (BP). This work represents the puzzle grid …

Algorithms Analysis System: Recurrences, Anchit Sharma

Master's Projects

Algorithms which are recursive have running times which can be described by

recurrence equations or recurrences. These equations determine the overall running time complexity of the algorithm. This project intends to create a mechanism for

• auto generating recurrence equations of the form T(n) = a(T(n)/b) + f(n)

• creating a computational method for solving them and generating running times

  i.e. O (f(n)) or Ω (f(n)).

• presenting students with a way to verify their manually computed answers with

  the solution generation by the project

• generating grading and feedback for their solution

  The exercises will utilize the ‘Substitution Method’ and the ‘Master Method’ …

  ---

  Go to article

Decompiler For Pseudo Code Generation, Ankit Patel

Master's Projects

Decompiling is an area of interest for researchers in the field of software reverse engineering. When the source code from a high-level programming language is compiled, it loses a great deal of information, including code structure, syntax, and punctuation.
The purpose of this research is to develop an algorithm that can efficiently decompile assembly language into pseudo C code. There are tools available that claim to extract high-level code from an executable file, but the results of these tools tend to be inaccurate and unreadable.
Our proposed algorithm can decompile assembly code to recover many basic high-level programming structures, including …