Competition GraphHPC-2017 for the fastest implementation of the task of Betweenness Centrality

The DISLab Laboratory ( JSC NICEVT ), together with the Research Center of the Moscow State University, hold the fourth annual scientific and practical conference on the parallel processing of large graphs using supercomputer complexes and cluster systems.

The purpose of the conference is to draw attention to the subject of tasks related to supercomputer processing of graphs and to provide a platform for communication between developers of technologies for supercomputer processing of graphs and developers of graph applications, discussing the prospects for this direction.

Very soon, within the framework of this scientific and technical conference GraphHPC-2017 , the GraphHPC competition will start, dedicated to the problems of parallel processing of large graphs using supercomputers. This time, participants will receive the fastest possible implementation of the Betweenness Centrality task in an undirected graph.

To implement the task participants are offered two categories of computing systems:

• One node that contains 2x Intel Xeon E5-2683v3 CPUs and an NVIDIA GPU K20x GPU. It is possible to use either only two CPUs, or one GPU, or all together;
• Multisite cluster with 36 computing nodes, connected by high-speed network "Angara"

Students, graduate students, young scientists and IT specialists are invited to participate in the competition, for whom GraphHPC can be a real chance to declare themselves to the scientific community and leading IT companies. On the contest website , you can familiarize yourself with the condition of the problem and download an example implementation written in C ++ (which includes a template for implementing its solution, the necessary infrastructure for generating graphs, a program for checking the correctness of the implemented solution for debugging).

The competition will be held from February 1 to February 27, 2017 with the help of an automatic system that will start operating from February 1. But now you can start working on a solution. Summing up on March 2, 2017 at the GraphHPC-2017 conference.

Winners and creatively distinguished participants will receive valuable prizes, as well as they will be able to speak at the conference, talking about their implementation of the task. For students there is a separate nomination!

Practical application of graph analysis.

Social network analysis is a study of social networks that considers social relationships in terms of network theory. These terms include the concept of a node (displays an individual participant within the network) and communication (displays such relationships between individuals as friendship, kinship, position in the organization, intimate relationships, etc.). These networks are often described as social network schemes, where nodes are represented as points, and links are represented as lines.
For the analysis of networks there is a set of well-known metrics:

Connections

• Homophily: the degree to which similar participants form connections with each other in comparison with dissimilar ones. Similarity can be determined by gender, race, age, occupation, academic achievement, status, values, or other prominent characteristics. The concept of homogeneity is associated with assortativeness.
  
  
• Multiplexity: The number of forms contained in a link. For example, two people who are friends and work together will have a multiplicity of 2. Multiplicity is related to the strength of a relationship.
  
  
• Mutuality / Reciprocity: the degree to which two participants reciprocate each other in the field of friendly or other interactions.
  ')
  
• Network Closure: A measure of the completeness of relational triads. Assigning the degree of network closure to individuals (that is, the fact that their friends are also friends with each other) is called transitivity. Transitivity is a consequence of an individual or situational feature consisting in the need for cognitive closeness.
  
  
• Neighborhood (Propinquity): the tendency of participants to have more connections with those who are closer in terms of geography.

Distribution

• Bridge : An individual whose weak links fill structural gaps, providing a single connection between two individuals or clusters. It also includes the shortest path when a longer path is not possible due to the high risk of message corruption or undeliverable.
  
  
• Centrality: centrality refers to a group of metrics whose purpose is to determine the “significance” or “influence” (in various meanings) of a particular node (or group) in a network. Examples of common methods for measuring “centrality” are the definition of centrality by mediation , centrality by proximity, centrality of an eigenvector, alpha centrality and centrality by degree.
  
  
• Density: the ratio of direct connections in the network to the total possible number of connections.
  
  
• Distance : the minimum number of connections required to connect two specific participants, as shown by Stanley Milgrem in his experiment and in the theory of six handshakes.
  
  
• Structural holes: no links between the two parts of the network. Finding and using a structural gap can give an entrepreneur a competitive advantage. This concept was developed by sociologist Ronald Burt. It is sometimes referred to as an alternative concept of social capital.
  
  
• Tie Strength: determined by a linear combination of time, emotional intensity, closeness and reciprocity (i.e. reciprocity). Strong bonds are determined by homogeneity, kinship and transitivity, while weak bonds are determined by bridges.

Segmentation

• A group is defined as a “clique” if each individual in it is directly connected with another individual. A group is defined as a “social circle” if it has fewer requirements for direct contact, which may not be defined.
  
  
• Clustering Ratio: a measure of the probability with which two partners of the same node are pals. A high coefficient of clustering corresponds to a significant click-through.
  
  
• Cohesion: the degree to which participants are connected directly with each other through social connections. Structural cohesion means the minimum number of participants who, when removed from a group, disintegrate the group.

References:

1. Social Network Analysis
2. Betweenness centrality
3. U. Brandes. A Faster Algorithm for Betweenness Centrality. 2001. A Faster Algorithm for Betweenness Centrality (English paper, PDF)