---
# System prepended metadata

title: Exploitable Features search

---

# Exploitable Features search

## GRAPH SIZE FEATURES

- Ratio (m/n   &   n/m)
- Density of a graph 
    |E| = num. of edges
    |V| = num. of vertices
    ->     2*|E| / |V| * (|V|-1)
    
    
    dense graph | sparse graph : 
      > 1/2          <1/2
        

## NODE DEGREE 

- median
- variation coefficient
- entropy

## MAXIMAL CLIQUE

## CLUSTERING COEFFICIENT
- Calculate triangles in a graph
    (for feature : clustering coefficient)
    ![](https://i.imgur.com/vy2mVxl.png)

  // it needs : ordered pair of vertices, in this case            alphabetically but they are sorted based on the maximum      num. of edges per single vertex
  
   ( also the largest and the smallest number of edges per         v. could be a relevant feature btw )
   
   https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/scoring/ClusteringCoefficient.java
   
   



## TREE DECOMPOSITION
- Cyclic Graph



## GREEDY COLORING (comparison between algorithms)
- n. colors needed
- time needed
- ratio (k_algorithm1/ k_algorithm2) & vicev.
- best coloring
- indipendent set size

## LOWER- UPPER BOUND
- distance
- ratio

## Graph Type

The below graph-types [1] have been found to which make finding the chromatic number faster and easier.

### Null Graph
- Denoted as `Nn`
- There are 0 edges between its vertices.
- An empty Graph
- Chromatic number is (at most) 1.

### Trivial Graph
- A graph with only 1 vertex
- Chromatic number is always `1`.

### Complete Graph
- denoted as `Kn`
- All possible edges
- Every pair of vertices is joined by exactly 1 edge.
- Contains `nC2` edges.
- Chromatic number is `n` (every vertex has a different color)

### (complete) Bipartite graph
- partition graph into two sets such that edges only go between sets, not within them.
- graph `G(V, E)` is bipartite if its vertex-set `V(G)` can be decomposed into 2 non-empty disjoint subsets `v1(G)` and `V2(G)` in such a way that each edge `e ∈ E(G)` has its one last joint in `V1(G)` and other last point in `V2(G)`.
- 2-Colorable
- Chromatic number is (at most) `2`.

### Star Graph
- denoted as `Sn`
- Complete bipartite graph
- `n-1` vertices have degree 1
- a single vertex has degree `n-1`.
- Simply said: 1 central vertex that is connected with all other vertices only.
- Chromatic number is (at most) `2`.

### Wheel Graph
- `n-1` vertices have degree 2
- a single vertex has degree `n-1`.
- Simply said: 1 central vertex that is connected with all other vertices only.
- Chromatic number is  `3` for odd wheels.
- Chromatic number is  `4` for even wheels.


### Cycle Graph
- in an undirected graphs cycles are the group of vertices that are related like in a polygon
- Chromatic number is 2 for even graphs
- Chromatic number is 3 for odd graphs

## Sources
[1]“Graph Theory Types of Graphs - javatpoint,” www.javatpoint.com. https://www.javatpoint.com/graph-theory-types-of-graphs (accessed Jan. 05, 2021).


# Hidden Features search
## LOCAL SEARCH PROBING FEATURES (?)
(most important for the training )
includes search for Local Optima and relative time


