CN105574131B - Social network friend making recommendation method and system based on dynamic community identification - Google Patents

Abstract

The invention discloses a social network friend recommendation method and system based on dynamic community identification, and belongs to the technical field of the Internet. The system function is mainly composed of the following four parts: community identification module, community classification module, friend recommendation module and result display module. A social network friend recommendation method based on dynamic community identification includes the following steps: step 1, obtain the user's second-degree friend list from the user-designed relational database, perform community identification, and calculate community correlation indicators; step 2, based on community correlation indicators Calculate the results and classify the obtained communities; step 3, recommend friends according to the classification results of the communities, and display the friend recommendation results by community categories. This method uses dynamic community identification and community attribute analysis to find and recommend people that users may be interested in.

Description

A social network friend recommendation method and system based on dynamic community identification

technical field

The invention belongs to the technical field of the Internet, and in particular relates to a method and system for recommending friends in a social network based on dynamic community identification.

Background technique

Current social network and software friend recommendation methods are mainly based on user similarity measures in social networks. Representative products and functions include People You May Know on Tencent QQ, People You May Know on Facebook, etc. The common feature of these methods is that potential friends with more mutual friends are more likely to be recommended.

However, in practical applications, the effect of social network friend recommendation is poor. The existing social network friend recommendation methods are faced with a dilemma: the recommended people know each other, but they are unwilling to be friends. There are two problems in this: (1) potential friends with more mutual friends are often the part that the user is not interested in in a mature community that the user joins. For example, if the user has added 80% of the classmates in the high school class as friends, then the number of mutual friends with the remaining 20% is very high, but the remaining 20% may not be willing to be friends; 80% of the colleagues in the unit, but the remaining 20% of the leaders are unwilling to be friends; (2) On the contrary, some potential friends with fewer mutual friends may be because the community is being formed. For example, in a newly enrolled college class, everyone is in the stage of getting to know each other and is familiar with each other. Such potential friends do not have a high number of common friends, but users are more interested in it. These reasons together lead to the inaccuracy of friend recommendation based on similarity measure.

Contents of the invention

In order to overcome the above-mentioned defects in the prior art, the purpose of the present invention is to provide a social network friend recommendation method and system based on dynamic community identification.

The present invention is achieved through the following technical solutions:

The invention discloses a social network friend recommendation method based on dynamic community identification, which includes the following steps:

Step 1: Obtain the user's second-degree friend list from the user-designed relational database, identify the community, and calculate the community correlation index;

Step 2, classify the obtained communities based on the calculation results of the community correlation index;

Step 3: According to the community classification results, recommend friends, and display the friend recommendation results by community categories.

In Step 1, obtain the user's second-degree friend list from the user-designed relational database, and perform community identification. The specific operations are:

1) Obtain the friend ID list of the target user, which is the first-degree friend list of the user; then obtain the friend ID list of each friend of the target user, which is the second-degree friend list of the user; merge the first-degree friend list and the second-degree friend list, If there are duplicates, delete the records in the second-degree friend list, and the merged list is a list of all friend IDs;

2) Determine whether there is a friend relationship between any two IDs in all friend ID lists, and construct an adjacency matrix;

3) Based on the adjacency matrix, perform community identification on the network composed of all friend ID lists, and output the community to which each ID belongs.

The calculation of the community correlation index mentioned in step 1 refers to the calculation of the community relationship density, the average establishment time of the community relationship, the connection density between the user and the community, and the average establishment time of the relationship between the user and the community for the community to which each ID belongs.

The calculation method of community correlation index is as follows:

Community relationship density = number of friendships in the community * 2 / [number of IDs in the community * (number of IDs in the community - 1)];

The average establishment time of the community relationship = the sum of the establishment time of the relationship in the community / the number of friendship relationships in the community;

The connection density between users and communities = the number of friendships between users and IDs in the community/the number of IDs in the community;

The average establishment time of the relationship between the user and the community = the sum of the establishment time of the friendship between the user and the ID in the community / the number of the friendship between the user and the ID in the community.

The second step is to classify the community, the specific operation is as follows:

1) Based on the community relationship density and the average establishment time of the community relationship, the community is divided into mature community, growing community and initial community;

Among them, it is defined that the average establishment time of the community relationship is longer than 180 days as a mature community; the average establishment time of the community relationship is less than or equal to 180 days but greater than 30 days is a growing community; the average establishment time of the community relationship is less than or equal to 30 days is an initial community;

2) Based on the connection density between the user and the community and the average establishment time of the relationship between the user and the community, the community is classified, and the community is divided into the user has entered the community, the user is entering the community, and the user is not related to the community;

Among them, it is defined that the user has entered the community if the connection density between the user and the community is greater than 0.6; the user is entering the community if the connection density between the user and the community is greater than 0.1 but less than or equal to 0.6; the user is not in the community if the connection density between the user and the community is less than or equal to 0.1 related societies.

In Step 3, recommend friends according to the community classification results. The specific operations are as follows:

When the community is not related to the user, no action is triggered;

When the community is that the user has entered the community, no action is triggered;

When the community is a growing community or an initial community, and the user is entering the community, the top 10 to 100 potential friends with the highest number of mutual friends are recommended according to the number of common friends of the community members and the user, sorted from high to low;

When the community is a mature community and the user is entering the community, according to the number of common friends with the user, sort from high to low, and recommend the top 1 to 3 potential friends with the highest number of common friends;

After establishing contact with these potential friends, other potential friends are gradually displayed in descending order of the number of common friends.

As described in step 3, display the friend recommendation results through the community category, and the specific operations are as follows:

When displaying the recommendation results of the community that is being formed, the user can see the top 10 to 100 potential friends at one time, and can add these potential friends as friends;

When displaying the recommendation results of the community you are entering, the user can only see the top 1 to 3 potential friends, and the other potential friends are displayed in grayscale, without complete information, and cannot be operated. As the user adds to this community Gradually let go as the number of friends increases.

The invention also discloses a social network friend recommendation system based on dynamic community identification, the system includes:

The community identification module is used to obtain the user's second-degree friend list from the user's social relationship database, perform community identification, and calculate community correlation indicators;

a community classification module for classifying identified communities;

The friend recommendation module is used to recommend the obtained community categories;

The result display module displays the friend recommendation results according to the community category.

The community classification module classifies the identified communities based on the community correlation index calculated by the calculation community identification module.

The friend recommendation module makes recommendations based on the obtained community category results.

Compared with the prior art, the present invention has the following beneficial technical effects:

The method for recommending social network friends based on dynamic community identification disclosed by the present invention first obtains the user's second-degree friend list from the user-designed relational database, performs community identification, and calculates the community correlation index at the same time; secondly, based on the calculation result of the community correlation index , to classify the obtained communities; thirdly, according to the community classification results, recommend friends, and recommend members who are entering the community and the initial community for the user. Recommend old relationships in outdated communities, avoid recommending a large number of relationships that have not entered the community to users, and avoid privacy leakage; finally, display friend recommendation results through community categories. The method of the present invention finds and recommends people who may be interested in the user through the method of dynamic community identification and community attribute analysis; "People", making recommendations based on users' current social interests, with higher recommendation accuracy and avoiding excessive user harassment and privacy leakage.

The invention also discloses a system capable of realizing the above friend recommendation method. The system function is mainly composed of the following four parts: a community identification module, a community classification module, a friend recommendation module and a result display module. First, the community identification module obtains the user's second-degree friend list from the user's social relationship database, performs community identification, and calculates some key indicators of the community. Based on the calculation results, the community classification module classifies the obtained communities. The friend recommendation module makes recommendations based on the obtained community categories. Finally, the result display module displays the friend recommendation results according to the community category.

Description of drawings

Fig. 1 is the logical structural diagram of the social network friend recommendation system based on dynamic community identification of the present invention;

FIG. 2 is an explanatory diagram of a friend list involved in the present invention;

Fig. 3 is a diagram showing the result of friend recommendation in social network based on dynamic community identification in the present invention.

Wherein, 101 is a community identification module; 102 is a community classification module; 103 is a friend recommendation module; 104 is a result display module.

detailed description

The present invention will be further described in detail below in conjunction with specific embodiments, which are explanations of the present invention rather than limitations.

The present invention discloses a social network friendship recommendation system based on dynamic community identification. Its functional structure is shown in Figure 1, wherein, 101 is a community identification module; 102 is a community classification module; 103 is a friend recommendation module; module.

The system function is mainly composed of the following four parts: community identification module, community classification module, friend recommendation module and result display module.

A social network friend recommendation method based on dynamic community identification includes the following steps:

Step 1: Obtain the user's second-degree friend list from the user-designed relational database, identify the community, and calculate the community correlation index;

Step 2, classify the obtained communities based on the calculation results of the community correlation index;

Step 3: According to the community classification results, recommend friends, and display the friend recommendation results by community categories.

The following is a specific example of the work of each module:

1. Community identification module

The first step is to obtain the target user's friend ID list, which is called the user's first-degree friend ID list, such as AB C D in FIG. 2 . The friend ID list of each friend of the user is called the user’s second-degree friend ID list, C D E F G in Figure 2; the first-degree friend ID list and the second-degree friend ID list are merged, and if duplicates are encountered, the second-degree friend ID is deleted The records in the list, such as CD in Figure 2, are only called first-degree friends. The merged list is called a list of all friend IDs, such as A B C D EF G in Fig. 2 .

The second step is to judge whether there is a friend relationship between any two IDs in the list of all friend IDs, and construct an adjacency matrix. For example, a value of 1 at position (i, j) of the matrix indicates that there is a friend relationship between the i-th ID and the j-th ID; 0 means that there is no friend relationship.

The third step is to perform community detection (Community Detection) on the network composed of all friend ID lists based on the adjacency matrix. There are already mature technical solutions for community identification. For details, you can refer to common methods such as Modularity ([1]Newman, M.E.J.2004."Fast algorithm for detecting community structure innetworks,"Physical Review E(69:6), p 066133.;[ 2] Newman M E J. Modularity and community structure in networks [J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.). After the community identification is completed, output the community to which each ID belongs. For example, the calculation result may be that IDs 1001, 1002, and 1003 belong to community 1; IDs 1004, 1005, and 1006 belong to community 2.

The fourth step is to calculate the community relationship density, the average establishment time of the community relationship, the connection density between users and the community, and the average establishment time of the relationship between users and the community for each community. in:

Community relationship density = number of friendships in the community * 2 / (number of IDs in the community * (number of IDs in the community - 1))

The average establishment time of the community relationship = the sum of the establishment time of the relationship in the community / the number of friendships in the community

The connection density between users and communities = the number of friendships between users and IDs in the community/the number of IDs in the community

The average establishment time of the relationship between the user and the community = the sum of the establishment time of the friendship between the user and the ID in the community / the number of the friendship between the user and the ID in the community.

For example, assuming that there are 4 IDs in the community including 1001, 1002, 1003, and 1004, the existing relationships include 1001-1002 (20 days), 1001-1003 (20 days), 1002-1004 (50 days), and 1003-1004 (30 days); the user has a friend relationship with 1001 (20 days), and a friend relationship with 1003 (30 days).

Then it can be calculated:

Community relationship density = 4*2/(4*3) = 0.67

The average establishment time of community relationship = (20+20+50+30)/4=30

Connection density between users and communities = 2/4 = 0.5

The average establishment time of the relationship between the user and the community=(20+30)/2=25.

2. Community classification module

1) This module first classifies communities based on the calculated community relationship density and the average establishment time of community relationships, and divides them into three categories: mature communities, growing communities, and initial communities.

One possible classification method is:

The average establishment time of the association relationship is longer than 180 days: it is called a mature association;

The average establishment time of the community relationship is less than or equal to 180 days but greater than 30 days: it is called a growing community.

The average establishment time of the community relationship is less than or equal to 30 days: it is called the initial community.

2) This module also classifies communities based on the connection density between users and the community, and the average establishment time of the relationship between the user and the community, and is divided into the user has entered the community, the user is entering the community, and the user is not related to the community.

One possible way is:

The connection density between the user and the community is greater than 0.6: the user has entered the community

The link density between the user and the community is greater than 0.1 but less than or equal to 0.6: it is said that the user is entering the community

The link density between users and communities is less than or equal to 0.1: it is called user-unrelated communities.

3. Friend recommendation module

When the community is not related to the user, no operation will be triggered (privacy protection);

When the community is that the user has entered the community, no action is triggered (to avoid over-recommendation of old relationships);

When the community is a growing community or an initial community and the user is entering the community, sort from high to low according to the number of common friends between the community members and the user, and recommend a larger number of potential friends with the highest number of common friends;

When the community is a mature community and the user is entering the community, according to the number of common friends with the user, sort from high to low, and recommend a smaller number of potential friends with the highest number of common friends; after establishing contact with these potential friends, Then gradually display other potential friends in descending order of the number of mutual friends.

4. Recommendation result display module

The result display module displays the recommendation result obtained by the above calculation to the user. See Figure 3. When displaying the recommendation results of a community that is being formed, the user can see a large number of potential friends at one time and add these potential friends as friends; while showing the recommendation results of a community that is entering, the user can only Seeing a small number of potential friends, other potential friends are displayed in grayscale, complete information is not displayed, and operations cannot be performed. As the number of friends added by users in this community increases, it will gradually be released.

When displaying the recommendation results of the community that is being formed, the user can see the top 10 to 100 potential friends at one time, and can add these potential friends as friends;

When displaying the recommendation results of the community you are entering, the user can only see the top 1 to 3 potential friends, and the other potential friends are displayed in grayscale, without complete information, and cannot be operated. As the user adds to this community Gradually let go as the number of friends increases.

Claims (4)

1. it is a kind of based on dynamic corporations recognize social networks friend-making recommendation method, it is characterised in that comprise the following steps：

Step one, obtains two degree of buddy lists of user from user's design relation database, carries out corporations' identification, while calculating society Group's correlation metric；

Two degree of buddy lists of user are obtained in the design relation database from user, corporations' identification is carried out, concrete operations are：

1) good friend's ID lists of targeted customer are obtained, is the once buddy list of the user；Each for obtaining targeted customer again is good Good friend's ID lists of friend, are two degree of buddy lists of the user；Merge once buddy list and two degree of buddy lists, if there is weight It is multiple, then the record in two degree of buddy lists is deleted, the list after merging is whole good friend's ID lists；

2) in judging whole good friend's ID lists, friend relation is whether there is between any two ID, builds adjacency matrix；

3) based on adjacency matrix, corporations' identification is carried out to the network of whole good friend ID lists composition, exports what each ID belonged to Corporations；

Described calculating corporations correlation metric, refers to that the corporations belonged to for each ID calculate corporations' relation density, corporations' relation The Connection Density for averagely setting up duration, user and corporations and the relation of user and corporations averagely set up duration；Specifically, corporations Correlation metric computational methods are as follows：

Friend relation number * 2/ [ID numbers * (ID numbers -1 in corporations) in corporations] in corporations' relation density=corporations；

The friend relation number set up in duration sum/corporations for averagely setting up relation in duration=corporations of corporations' relation；

User and the Connection Density=user of corporations and ID numbers in the friend relation number/corporations of ID in corporations；

The relation of user and corporations averagely set up duration=user and the friend relation of ID in corporations set up duration sum/user with The friend relation number of ID in corporations；

Resulting corporations, based on corporations' correlation metric result of calculation, are classified by step 2；

Step 3, according to corporations' classification results, carries out friend recommendation, and shows friend recommendation result by corporations' classification.

2. it is according to claim 1 based on dynamic corporations recognize social networks friend-making recommendation method, it is characterised in that step It is as follows that rapid two pairs of corporations carry out classification concrete operations：

1) duration is averagely set up based on corporations' relation density and corporations' relation, corporations during corporations are divided into ripe corporations, are grown up With initial corporations；

Wherein, define corporations relations averagely set up duration more than 180 days for ripe corporations；It is little that corporations' relation averagely sets up duration In equal to 180 days but more than 30 days for growth in corporations；Corporations' relation averagely sets up duration less than or equal to 30 days for initial Corporations；

2) a length of corporations' classification when averagely being set up with the relation of corporations based on the Connection Density and user of user and corporations, by corporations It is divided into user and has been enter into corporations, user and is going into corporations and the uncorrelated corporations of user；

Wherein, define user and have been enter into corporations for user more than 0.6 with the Connection Density of corporations；User is close with the connection of corporations Degree more than 0.1 but is going into corporations less than or equal to 0.6 for user；User is less than or equal to 0.1 with the Connection Density of corporations For the uncorrelated corporations of user.

3. it is according to claim 2 based on dynamic corporations recognize social networks friend-making recommendation method, it is characterised in that step Friend recommendation is carried out according to corporations' classification results described in rapid three, concrete operations are：

When corporations uncorrelated for user of corporations, any operation is not triggered；

When corporations have been enter into corporations for user, any operation is not triggered；

When corporations are corporations or initial corporations in growing up, and when being going into corporations for user, according to incorporator with user's Common friend number number, sort from high to low, recommend common friend number highest before 10 to 100 potential good friends；

When corporations are ripe corporations, and when being going into corporations for user, according to the common friend number of user number, from height To low sequence, recommend the potential good friend of 1 to 3 before common friend number highest；

After contacting with these potential good friends' foundation, then gradually show that other are potential good from more to few order according to common friend number Friend.

4. it is according to claim 3 based on dynamic corporations recognize social networks friend-making recommendation method, it is characterised in that step Friend recommendation result is shown by corporations' classification described in rapid three, concrete operations are：

During the recommendation results of the corporations that displaying is being formed, user can disposably see first 10 to 100 potential good friends, and These potential good friends can be added as a friend；

And when showing the recommendation results of the corporations being going into, user can only see first 1 to 3 potential good friends, other potential Good friend's gray scale show, do not show complete information, can not operate, with user in this corporation plus increasing for good friend's quantity and Gradually relax control.