Research Case Study Abstract

This research project is about implementing algorithms for signed graphs.

Definitions

Signed Graph :

A signed graph is a mathematical structure that represents relationships between entities, where each edge has a positive or negative sign. Positive edges typically represent friendly or positive relationships, while negative edges represent hostile or negative relationships. Signed graphs are used to model complex social, political, or interaction networks where relationships can have different polarities.

Balanced graph :

An Signed-graph is balanced if and only if its points can be separated into two mutually exclusive subsets such that each positive line joins two points of the same subset and each negative line joins points from different subsets.

Weakly balanced graph :

A graph is weakly balanced if there are no cycles in the graph with exactly one negative degree. Also its vertices can be split into k>=1 groups(clusters), such that edges within groups are positive and edges between groups are negative.

K-Balanced :

K-balanced refers to the property of a signed graph where it can be divided into k (where k is a positive integer) distinct groups or clusters. Inside each group, the relationships are predominantly positive, while between groups, they are mostly negative. It's a way to partition a signed graph into cohesive subgroups with fewer negative connections across the groups.

Depth First Search :

Depth First Search is an algorithm used to traverse or search through a graph or tree structure. It starts at a selected node and explores as far as possible along each branch before backtracking. It's a way to systematically visit all the vertices in a graph, useful for tasks like finding paths, cycles, or connectivity information in graphs.

Adjacency list :

An adjacency list is a way to represent a graph in data structures. In this representation, each vertex in the graph has a list of its adjacent vertices. It's a compact way to store graphs, especially sparse ones, and it's efficient for tasks like finding neighbors of a vertex.

General Information (Cycle, Path) :

In the context of graphs, a "cycle" is a closed path that starts and ends at the same vertex, meaning you can follow edges to return to your starting point. A "path" is a sequence of vertices where each adjacent pair is connected by an edge. Paths can be open (from one vertex to another) or closed (a cycle). These concepts are fundamental in graph theory for understanding connectivity and structure in graphs.

Reference

Files Shared By Prof.

•	Clustering and Structural Balance in Graphs (James A. Davis)
•	The Psychological Review(Dorwin Cartwright, Frank Harary) 
•	Correlation Clustering(Nikhil Bansal, Avrim Blum, Shuchi Chawla)

Files used in researching: (Could be useful in preparation of final report)

•	Encyclopedia of Social Network Analysis and Mining-Springer New York (2018): (Page 2498 of "Reda Alhajj, Jon Rokne) 
https://link.springer.com/referencework/10.1007/978-1-4939-7131-2
•	A Simple Algorithm To Detect Balance In Signed Graphs: Frank Harary and Jerald A. Kabel
https://www.sciencedirect.com/science/article/pii/0165489680900104
•	Spectral Theory of Unsigned and Signed Graphs Applications to Graph Clustering: a Survey Jean Gallier: (Chapter-5)

Suggestion from Prof.

• Start using overleaf • Do task reports and presentations in LATEX.

LATEX Ref :

https://www.youtube.com/watch?v=VhmkLrOjLsw&t=1397s
https://de.overleaf.com/gallery
http://people.duke.edu/~hpgavin/tutorial.pdf
http://tobi.oetiker.ch/lshort/lshort.pdf
http://en.wikibooks.org/wiki/LaTeX
http://www.cs.berkeley.edu/~daw/teaching/cs70-s08/tut.pdf
http://www.maths.tcd.ie/~dwilkins/LaTeXPrimer/
http://www.tug.org/twg/mactex/tutorials/ltxprimer-1.0.pdf
http://ece.uprm.edu/~caceros/latex/introduction.pdf
http://heather.cs.ucdavis.edu/~matloff/latex.html
http://www.cs.cornell.edu/info/misc/latex-tutorial/latex-home.html
http://csil.cs.uchicago.edu/assets/latex_tutorial.pdf

Note : You can add your valuable information