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!

  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.