# How to shrink an undirected graph?

Let's say I have an undirected graph of students and their friendship ratings like in the following format:

Person 1 (Student ID)  Person 2 (Student ID)  Strength (Out of 5)
A                      B                      5
K                      E                      3


The data is simple, but the problem is that my dataset is too big and I am trying to analyze ~ 1 million relationships. What are some of the processes I can use to reduce this graph and calculate things like centrality? I also would like to make it small enough so I can visualize it in Gephi. Let me know your thoughts!

• unbalanced classes refers classification problems in which the minority class size is much smaller than the majority class. This tag is not related to this question. – DaL Dec 19 '16 at 7:08

Intersting question.

It seems that you are interested in a lossy reduction, one from which you cannot construct back the input. In order to choose the proper lossy reduction, one should define the goal and than look for a scheme that minimise the reduction with respect to the goal.

I make some assumptions here:

• You discuss students so each student (a node) has not too many (dozens? hundreds?) relations (edges)
• You have ~ million relations so you have students from some universities.
• Therefore, most edges are local (between students from the same university or even faculty).

I would have try these directions: Take a sample of the students. The graph obtained from the samples will represent the universities.

You can also take only students with a high number of edges those with few edges tend to have less impact of the graph structure.

You might be interested in combining the two directions above: identify local structures and then create a sub graph of students of many edges or connecting some structures.

You might also try Dbscan, a clustering algorithm based on graphs that might be handy here.