CN101887573A - Method and system for social network clustering association analysis based on core points - Google Patents

Abstract

The present invention provides a social network clustering association analysis method and system based on core points, wherein the method includes: obtaining the stable time period of the social network; approximating the social network in the stable time period to obtain an approximate graph of the social network; The maximum cliques in the social network approximation graph; according to the proportion of the common points between the maximum cliques to the corresponding maximum cliques, merge the maximum cliques to obtain the community; according to the similarity, associate the communities at different times. The present invention approximates the obtained social network in a stable time period, and this approximation method can effectively reduce the influence of noise in subsequent analysis, and meanwhile retain the basic features of the social network, making the analysis result more accurate. In the process of discovering communities, directly merging extremely large groups can quickly discover communities, and then quickly obtain analysis results.

Description

Method and system for social network clustering association analysis based on core points

technical field

The invention relates to a core point-based social network clustering association analysis method and system.

Background technique

At present, the objects processed by data mining tasks are mainly individual data instances, which can often be represented by a vector containing multiple attribute values, and these data instances are assumed to be statistically independent. For example, to train a disease diagnosis system, its task is to diagnose whether a subject suffers from a certain infectious disease, the usual practice is to use a vector to represent a subject, and at the same time assume that the relationship between the subjects The disease conditions are independent of each other, that is, knowing a confirmed patient does not provide any help in diagnosing whether other subjects have the disease. Intuitive experience tells us that this assumption is unreasonable. If a person's relatives and friends suffer from the infectious disease, he is more likely to get the disease than other people. In society, people are not simply statistically independent sampling points. There must be connections and influences between them. Ignoring this connection will have a great impact on the performance of the entire diagnostic system. In order to solve this problem, the relationship between data instances must be taken into account at the same time, thus the concept of social network is proposed, and the social structure can be described by graph structure.

A social network includes many nodes and one or more specific links connecting these nodes. Among them, nodes often represent physical entities such as individuals, groups, people, articles, and/or servers; links represent various relationships between nodes, such as friend relationships, kinship relationships, trade relationships, and reference relationships. In addition to graph structure representations, social networks have other representations in sociological and algebraic forms.

In many cases, links change over time, so the analysis of social networks requires the analysis of changes in social networks over a period of time. At present, the main method is to divide the time period of analysis into equal segments and perform segmental analysis, that is, incremental analyze. However, in the actual situation, the occurrence and development of things are not uniform, and the incremental analysis method cannot accurately analyze the noise and events in the social network. Among them, the noise refers to the connection that has nothing to do with the subject of social network analysis, mainly caused by the social network. It is caused by the randomness and uncertainty of individual behaviors, such as invalid calls caused by dialing the wrong phone number; events refer to abnormal connections related to the subject of social network analysis, such as people's calls during the Spring Festival. Incremental analysis methods, on the one hand, may amplify noise during the analysis process, or often fail to capture the evolution points (events) that have caused major changes in the development of things during this time period, and thus cannot provide accurate analysis results. How to quickly get Accurate analysis results directly affect the efficiency of social network analysis.

Contents of the invention

Therefore, the object of the present invention is to provide a method and system for analyzing social network clustering associations based on core points, so as to quickly obtain accurate analysis results.

In order to achieve the above-mentioned purpose of the present invention, a kind of core point-based social network clustering association analysis method and system are provided, including:

Get the stationary time period of the social network;

Approximating the social network in the stationary time period to obtain an approximate graph of the social network;

finding the maximal cliques in the social network approximation graph;

According to the proportion of the corresponding maximum cliques in the common points between the maximum cliques, the maximum cliques are merged to obtain a community;

According to the similarity, the associations at different moments are associated.

Preferably, said approximating the social network in the stationary period includes:

Initialize an empty network;

sorting the edge sets of the social network in the stationary time period;

Adding edge sets to the empty network in order until the deviation between the empty network and the social network in the stable time period is the smallest, and obtaining an approximate graph of the social network in the stable time period.

Preferably, the sort order is descending order.

Preferably, the merging of the maximal cliques according to the proportion of the corresponding maximal cliques of the common points between the maximal cliques includes:

When the number of common points between two maximal cliques is greater than or equal to the number of points of the maximal clique with fewer points minus N, merge the two maximal cliques, where N is greater than 0 and less than the number of points of the maximal clique with fewer points integer.

Preferably, said N is 1.

Preferably, the similarity includes community point coincidence and/or structural similarity.

Preferably, it also includes:

Analyze the tightness of said community structure;

And/or, analyzing the degree of uniformity of edge weight distribution among points in the community.

The present invention also provides a core point-based social network clustering association analysis method and system, characterized in that the system includes:

The stationary unit is used to obtain the stationary time period of the social network;

The approximation unit is used to approximate the social network in the stationary time period to obtain a social network approximation graph;

A calculation unit, used to find the maximal clique in the social network approximation graph;

The community unit is used to merge the maximum cliques according to the proportion of the corresponding maximum cliques in the common points between the maximum cliques to obtain the community;

The tracking unit is used to associate communities at different moments according to the similarity.

Preferably, the approximation unit includes:

Initialize subunits for initializing empty networks;

a sorting subunit, configured to sort the edge sets of the social network in the stationary time period;

The approximation subunit is configured to add edge sets to the empty network in order until the deviation between the empty network and the social network in the stationary time period is the smallest, and obtain an approximate graph of the social network in the stationary time period. The system also includes:

An analysis unit, configured to analyze the tightness of the community structure; and/or, analyze the uniformity of edge weight distribution among points within the community.

The beneficial effects of the present invention are:

The present invention approximates the obtained social network in a stable time period, and this approximation method can effectively reduce the influence of noise in subsequent analysis, and meanwhile retain the basic features of the social network, making the analysis result more accurate. On the basis of the approximate graph of the social network, the method of finding and merging the maximum clique is used to discover the community; the community is used as the core point of the subsequent clustering association, and in the process of discovering the community, the maximum clique is directly analyzed Merging, compared with the prior art to compare the maximum cliques, establish the association relationship between the maximum cliques according to the comparison results, and perform the merging of the maximum cliques according to the association relationship, the technical solution of the present invention saves a lot of storage space for the association relationship, And avoiding multiple comparisons before merging, communities can be quickly discovered, and then analysis results can be quickly obtained.

Description of drawings

Fig. 1 shows a schematic flow diagram of a social network clustering association analysis method based on core points in an embodiment of the present invention;

FIG. 2 shows a schematic diagram of the application process of the core point-based social network clustering association analysis method in the embodiment of the present invention;

FIG. 3 shows a schematic diagram of an approximate structure of a social network in a stationary time period in an embodiment of the present invention;

Fig. 4 shows a schematic structural diagram of a very large cluster in an embodiment of the present invention;

Fig. 5 shows a schematic structural diagram of community tracking in an embodiment of the present invention;

FIG. 6 shows a schematic structural diagram of a social network clustering association analysis system based on core points in an embodiment of the present invention.

Detailed ways

The core point-based social network clustering association analysis method and system of the present invention will be described in detail below with reference to the accompanying drawings. In order to avoid noise, the present invention uses an approximate graph structure to describe a social network in a steady evolution stage.

Please refer to Figure 1, a core point-based social network clustering association analysis method and system, including:

Get the stationary time period of the social network;

Approximating the social network in the stationary time period to obtain an approximate graph of the social network;

finding the maximal cliques in the social network approximation graph;

According to the proportion of the corresponding maximum cliques in the common points between the maximum cliques, the maximum cliques are merged to obtain a community;

According to the similarity, the associations at different moments are associated.

The approximation of the social network in the stationary time period includes:

Initialize an empty network;

sorting the edge sets of the social network in the stationary time period;

Adding edge sets to the empty network in order until the deviation between the empty network and the social network in the stable time period is the smallest, and obtaining an approximate graph of the social network in the stable time period.

Preferably, the sort order is descending order.

Preferably, the merging of the maximal cliques according to the proportion of the corresponding maximal cliques of the common points between the maximal cliques includes:

When the number of common points between two maximal cliques is greater than or equal to the number of points of the maximal clique with fewer points minus N, merge the two maximal cliques, where N is greater than 0 and less than the number of points of the maximal clique with fewer points integer.

Preferably, said N is 1.

On the basis of the approximate graph of the social network, the method of finding and merging the maximum clique is used to discover the community; the community is used as the core point of the subsequent clustering association, and in the process of discovering the community, the maximum clique is directly analyzed Merging, compared with the prior art to compare the maximum cliques, establish the association relationship between the maximum cliques according to the comparison results, and perform the merging of the maximum cliques according to the association relationship, the technical solution of the present invention saves a lot of storage space for the association relationship, And avoiding multiple comparisons before merging, communities can be quickly discovered, and then analysis results can be quickly obtained.

Preferably, the similarity includes community point coincidence and/or structural similarity.

Preferably, it also includes:

Analyze the tightness of said community structure;

And/or, analyzing the degree of uniformity of edge weight distribution among points in the community.

The evolution of social network is a process of steady and alternating events. By extracting the features of the social network in two stable time periods before and after the event (evolution point), comparing their differences in these two time periods, we can accurately and quickly discover the occurrence of events in the network evolution process, and reveal the impact of the event on The impact of network evolution.

Please refer to Figure 2 for an example of the application of the core point-based social network clustering association analysis method:

201. Data: Accept social network data input by users;

202. Approximation of a stable time period: use a heuristic method to initialize an empty network, then sort the edge sets of the network in descending order, and continuously add them to the network in order, so that the deviation between the network after adding edges and the network of this time period minimum, and finally obtain an approximate graph of this time period, for example, please refer to FIG. The four networks of , they belong to the same stable time period, and the approximate figure 302 is an approximate figure of this time period;

Community findings include:

203. Find clique (maximum complete subgraph in the figure, i.e. maximum clique): for a given approximate graph, find all cliques, for example, please refer to Figure 4, there are two cliques, respectively {1, 2, 4 , 5} and {2, 3, 4};

204. Merge partial cliques: For any two cliques with common points, if the number of common points reaches the size-1 of the smaller clique of the two cliques (the value of size is the number of nodes in the maximum clique) , then the two cliques are merged. This step runs iteratively until no clique merging occurs again.

205. Divide overlapping nodes: divide overlapping nodes into one of the communities to obtain non-overlapping communities;

206. Absorb special nodes: absorb nodes that were not in a certain community;

207. Merge close associations: Merge closely related associations.

208. Community tracking: For the communities discovered at different times, consider the point coincidence and structural similarity of the communities, and associate them. For example, please refer to Figure 5, the figure d is most similar to the figure a;

209. Community evolution: According to the tracked community, the nature of the community is evaluated from the following two aspects: a) the tightness of the community structure; b) the uniformity of the edge weight distribution among the points within the community.

In the existing method of community discovery, it is necessary to establish an association relationship between cliques (whether there are k-1 common points) before merging cliques, and the establishment of this relationship requires multiple comparisons between cliques. When there are many clique structures in the figure and they are closely related, the efficiency of the method will be greatly affected; at the same time, a large number of relationships between cliques need to be saved, resulting in a large amount of memory overhead.

In the process of community discovery, this scheme adopts the immediate merging strategy, which improves the merging efficiency, saves memory overhead, and improves the analysis speed.

The present invention also provides a core point-based social network clustering association analysis method and system, characterized in that the system includes:

The stationary unit is used to obtain the stationary time period of the social network;

The approximation unit is used to approximate the social network in the stationary time period to obtain a social network approximation graph;

A calculation unit, used to find the maximal clique in the social network approximation graph;

The community unit is used to merge the maximum cliques according to the proportion of the corresponding maximum cliques in the common points between the maximum cliques to obtain the community;

The tracking unit is used to associate communities at different moments according to the similarity.

Preferably, the approximation unit includes:

Initialize the subunit, used to initialize the empty network;

a sorting subunit, configured to sort the edge sets of the social network in the stationary time period;

The approximation subunit is configured to add edge sets to the empty network in order until the deviation between the empty network and the social network in the stationary time period is the smallest, and obtain an approximate graph of the social network in the stationary time period. The system also includes:

An analysis unit, configured to analyze the tightness of the community structure; and/or, analyze the uniformity of edge weight distribution among points within the community.

Although the present invention has been described in detail above with reference to specific embodiments, those skilled in the art can make various modifications and variations to the present invention under the teaching herein without departing from the essence and scope of the present invention.

Claims (10)

1. social network clustering correlation analysis method and system based on a core point comprise:

Obtain the stationary time section of community network;

Community network to the stationary time section is similar to, and obtains the community network approximate diagram;

Obtain the very big group in the described community network approximate diagram;

Proportion according to the shared corresponding very big group of total point between the very big group carries out merger with described very big group, obtains corporations;

According to similarity, related different corporations constantly.

2. method according to claim 1, wherein, described community network to the stationary time section is similar to and comprises:

Initialization abortive haul network;

Limit collection ordering with the community network of described stationary time section;

In order the limit collection is added in the described abortive haul network,, obtain the community network approximate diagram of described stationary time section until the deviation minimum of the community network of described abortive haul network and described stationary time section.

3. method according to claim 2, wherein, described clooating sequence is a descending.

4. method according to claim 1, wherein, described basis is the proportion of the shared corresponding very big group of total point between the group greatly, described very big group is carried out merger comprise:

When two very big the counting when subtracting N more than or equal to the counting of few very big group of counting of total point between the group, with these two greatly group's merger, wherein, N is for greater than 0 integer less than few very big blob number of counting.

5. method according to claim 4, wherein, described N is 1.

6. method according to claim 1, wherein, described similarity comprises the some registration of corporations and/or the similarity of structure.

7. method according to claim 6 wherein, also comprises:

Analyze the tightness degree of described corporations structure;

And/or, analyze the degree of uniformity of limit weight distribution between the inner each point of described corporations.

8. social network clustering correlation analysis method and system based on a core point is characterized in that this system comprises:

Steady unit is used to obtain the stationary time section of community network;

Approximate unit is used for the community network of stationary time section is similar to, and obtains the community network approximate diagram;

Computing unit is used for obtaining the very big group of described community network approximate diagram;

The corporations unit is used for according to the proportion that greatly has the shared corresponding very big group of point between the group described very big group being carried out merger, obtains corporations;

Tracing unit is used for according to similarity, related different corporations constantly.

9. system according to claim 8 is characterized in that, described approximate unit comprises:

The initialization subelement is used for initialization abortive haul network;

The ordering subelement is used for the limit collection ordering with the community network of described stationary time section;

Approximate subelement is used in order the limit collection being added described abortive haul network, until the deviation minimum of the community network of described abortive haul network and described stationary time section, obtains the community network approximate diagram of described stationary time section.

10. according to Claim 8 or 9 described systems, it is characterized in that this system also comprises:

Analytic unit is used to analyze the tightness degree of described corporations structure; And/or, analyze the degree of uniformity of limit weight distribution between the inner each point of described corporations.

Images