CN111814944A - Method, device and terminal for allocating vertices to communities - Google Patents

Abstract

The embodiment of the invention provides a vertex-to-community distribution method, a device and a terminal, wherein the method comprises the following steps: distributing the plurality of vertexes to a plurality of communities to obtain a plurality of distribution sequences, wherein each distribution sequence comprises the plurality of vertexes and vertex positions corresponding to the vertexes; selecting a vertex position as a target position, and comparing a target vertex corresponding to the target position with the rest of vertices in each distribution sequence to obtain a plurality of vertex similarities corresponding to each distribution sequence; determining an allocation strategy according to the similarity of the plurality of vertexes; and obtaining the probability of the distribution strategy according to the random distribution probability value and the distribution strategy of the plurality of vertexes distributed to the plurality of communities. The final vertex assignment to the respective communities enables faster and better convergence to the optimal solution.

Description

Method, device and terminal for allocating vertices to communities

technical field

The present invention relates to the technical field of data analysis, and in particular, to a method, device and terminal for allocating vertices to communities.

Background technique

Humans are social animals, and objects also have categories. People are divided into groups and objects are clustered together. The situation of groups can be considered as the distribution of communities, and the vertices represent a single person or object. In order to make objects and people optimally discover group information, A distribution reward mechanism can be used. The reinforcement learning allocation strategy generally uses the Markov Decision Process (MDP) as the ideological basis. The Markov decision process refers to selecting an action from the available action set to make a decision according to the state observed at each moment, and the system goes to the next step. The (future) state is random and its state transition probabilities have Markov properties. The decision maker makes new decisions based on the newly observed state, and it is repeated to describe the probability of performing different actions in different states. The allocation strategy can make the allocation of vertices to the community jump out of the local solution and achieve the global solution as much as possible. The core of which is the strategy process. The strategy process determines the probability of apex-community allocation. Optimizing its allocation probability can optimize the process of learning allocation. The traditional learning strategy is a random assignment strategy. The random assignment probability value ε varies within a range. In the initial situation, the random assignment probability value ε is relatively large, and the randomness of vertices to the community is relatively high, and the probability value is randomly assigned in the subsequent process. When ε becomes smaller, it stabilizes to a certain distribution of vertices to the community, resulting in not well converged to the optimal solution.

SUMMARY OF THE INVENTION

Embodiments of the present invention provide a method, device, and terminal for allocating vertices to communities, so as to solve at least one or more technical problems in the prior art.

In a first aspect, an embodiment of the present invention provides a method for allocating vertices to communities, including:

A plurality of vertices are allocated to a plurality of communities to obtain a plurality of allocation sequences, each of the allocation sequences includes a plurality of the vertices, and a vertex position corresponding to each of the vertices;

Selecting a vertex position as the target position, in each of the allocation sequences, comparing the target vertex corresponding to the target position with the remaining vertices to obtain a plurality of vertex similarities corresponding to each of the allocation sequences;

determining an allocation strategy according to a plurality of the vertex similarities;

The probability of the assignment strategy is obtained according to the random assignment probability value and assignment strategy of multiple vertices assigned to multiple communities.

In one embodiment, multiple vertices are assigned to multiple communities to obtain multiple sets of assignment sequences, including:

其中，N≥1，K≥1，i≥1，N＞K。N vertices are allocated to K communities, and i allocation sequences are obtained. The N vertices include x ₁ , x ₂ ...... x _N , and the i allocation sequences include:

Among them, N≥1, K≥1, i≥1, N>K.

In one embodiment, a vertex position is selected as the target position, and in each of the allocation sequences, the target vertex corresponding to the target position and the remaining vertices are compared to obtain a plurality of vertex similarities corresponding to each of the allocation sequences, include:

Select a vertex position as the target position g;

与剩余顶点，得到的顶点相似度为

其中，i个分配序列对应的i个顶点相似度包括：Y₁，Y₂...Y_i。In the allocation sequence Xi, compare the target vertices corresponding to the target position _g

With the remaining vertices, the obtained vertex similarity is

Wherein, the i vertex similarities corresponding to the i allocation sequences include: Y ₁ , Y ₂ . . . Y _i .

In one embodiment, the allocation strategy is determined according to a plurality of the vertex similarities, including:

i为奇数，分配策略X'_i是i个分配序列中对应的目标顶点相同。When there are multiple vertex similarities greater than or equal to a preset threshold, the preset threshold is

i is an odd number, and the allocation strategy X' _i is that the corresponding target vertices in the i allocation sequences are the same.

In one embodiment, the allocation strategy is determined according to a plurality of the vertex similarities, including:

When there are multiple vertex similarities smaller than the preset threshold, the allocation strategy X' _i is to allocate adjacent vertices to K communities.

In one embodiment, the allocation strategy is determined according to a plurality of the vertex similarities, including:

i为奇数，分配策略X'_i是重新选择所述目标位置。When there is only one vertex similarity greater than or equal to the preset threshold, the preset threshold is

i is an odd number, and the allocation strategy X' _i is to reselect the target position.

In one embodiment, the probability of obtaining the assignment strategy is obtained according to the random assignment probability value and assignment strategy of multiple vertices assigned to multiple communities, including:

计算分配策略的概率，其中，多个顶点分配至多个社区的随机分配概率值为ε。Utilization

Calculate the probability of the assignment strategy, where the random assignment probability of multiple vertices to multiple communities is ε.

In a second aspect, an embodiment of the present invention provides an apparatus for allocating vertices to communities, including:

an allocation sequence acquisition module, configured to allocate a plurality of vertices to a plurality of communities to obtain a plurality of allocation sequences, each of the allocation sequences including a plurality of the vertices, and a vertex position corresponding to each of the vertices;

The vertex similarity calculation module is used to select a vertex position as the target position, in each of the allocation sequences, compare the target vertex corresponding to the target position with the remaining vertices, and obtain a plurality of vertex similarities corresponding to each of the allocation sequences ;

an allocation strategy determination module, configured to determine an allocation strategy according to a plurality of the vertex similarities;

The distribution strategy probability calculation module is used to obtain the probability of the distribution strategy according to the random distribution probability value and the distribution strategy of the multiple vertices allocated to the multiple communities.

In one embodiment, the allocation sequence acquisition module includes:

其中，N≥1，K≥1，i≥1，N＞K。The allocation unit is used to allocate N vertices to K communities, and obtain i allocation sequences. The N vertices include x ₁ , x ₂ ...... x _N , and the i allocation sequences include:

Among them, N≥1, K≥1, i≥1, N>K.

In one embodiment, the vertex similarity calculation module includes:

a target position selection unit for selecting a vertex position as the target position g;

与剩余顶点，得到的顶点相似度为

The similarity calculation unit is used to compare the target vertices corresponding to the target position g in the allocation sequence X _i

With the remaining vertices, the obtained vertex similarity is

The similarity set unit, used for the similarity of i vertices corresponding to the i allocation sequences, includes: Y ₁ , Y ₂ . . . Y _i .

In one embodiment, the allocation strategy determination module includes:

i为奇数，分配策略X'_i是i个分配序列中对应的目标顶点相同。The first allocation strategy unit is used when there are multiple vertex similarities greater than or equal to a preset threshold, wherein the preset threshold is

i is an odd number, and the allocation strategy X' _i is that the corresponding target vertices in the i allocation sequences are the same.

In one embodiment, the allocation strategy determination module includes:

The second allocation strategy unit is configured to allocate adjacent vertices to K communities when there are multiple vertex similarities less than a preset threshold, the allocation strategy X' _i .

In one embodiment, the allocation strategy determination module includes:

i为奇数，分配策略X'_i是重新选择所述目标位置。The third allocation strategy unit is used when there is only one vertex similarity greater than or equal to a preset threshold, wherein the preset threshold is

i is an odd number, and the allocation strategy X' _i is to reselect the target position.

In one embodiment, the distribution strategy probability calculation module includes:

计算分配策略的概率，其中，多个顶点分配至多个社区的随机分配概率值为ε。Probability calculation unit for using the formula

Calculate the probability of the assignment strategy, where the random assignment probability of multiple vertices to multiple communities is ε.

In a third aspect, an embodiment of the present invention provides an apparatus for allocating vertices to communities. The functions of the apparatus may be implemented by hardware, or by executing corresponding software in hardware. The hardware or software includes one or more modules corresponding to the above functions.

In a possible design, the structure of the vertex-to-community allocation device includes a processor and a memory, and the memory is used to store a program that supports the device to execute the above-mentioned vertex-to-community allocation method, the processor is is configured to execute a program stored in the memory. The apparatus for assigning vertices to communities may further include a communication interface for communicating with other devices or a communication network.

In a fourth aspect, an embodiment of the present invention provides a computer-readable storage medium for storing computer software instructions used by a vertex-to-community allocation apparatus, which includes a program for executing the above-mentioned vertex-to-community allocation method.

One of the above technical solutions has the following advantages or beneficial effects: In the process of the reinforcement learning strategy for assigning vertices to communities, the vertex assignment of the genetic algorithm is introduced as a guide, so that the final vertices are assigned to each community faster and better. converge to the optimal solution.

The above summary is for illustrative purposes only and is not intended to be limiting in any way. In addition to the illustrative aspects, embodiments and features described above, further aspects, embodiments and features of the present invention will become apparent by reference to the accompanying drawings and the following detailed description.

Description of drawings

In the drawings, unless stated otherwise, the same reference numbers refer to the same or like parts or elements throughout the several figures. The drawings are not necessarily to scale. It should be understood that these drawings depict only some embodiments according to the disclosure and should not be considered as limiting the scope of the invention.

FIG. 1 shows a flowchart of a method for allocating vertices to communities according to an embodiment of the present invention.

FIG. 2 shows a flowchart of another method for allocating vertices to communities according to an embodiment of the present invention.

FIG. 3 shows a strategy of joining MOEA and a distribution curve diagram of a non-MOEA algorithm of the Cornell community data set according to an embodiment of the present invention.

FIG. 4 shows a policy of joining MOEA and a distribution curve diagram of a non-MOEA algorithm of the political blog data set Polblogs Dataset according to an embodiment of the present invention.

FIG. 5 shows the strategy of joining MOEA and the distribution curve diagram of the non-MOEA algorithm of the Washington Washington community data set according to an embodiment of the present invention.

FIG. 6 shows a strategy of joining MOEA and a distribution curve diagram of a non-MOEA algorithm of the Wisconsin Wisconsin community data set according to an embodiment of the present invention.

FIG. 7 shows a schematic diagram of a method for allocating vertices to communities according to an embodiment of the present invention.

FIG. 8 shows a structural block diagram of an apparatus for allocating vertices to communities according to an embodiment of the present invention.

FIG. 9 shows a structural block diagram of another apparatus for allocating vertices to communities according to an embodiment of the present invention.

FIG. 10 shows a structural block diagram of a terminal for assigning vertices to communities according to an embodiment of the present invention.

Detailed ways

In the following, only certain exemplary embodiments are briefly described. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present invention. Accordingly, the drawings and description are to be regarded as illustrative in nature and not restrictive.

FIG. 1 shows a flowchart of a method for allocating vertices to communities according to an embodiment of the present invention. As shown in Figure 1, in one embodiment, the method includes:

Step S10: multiple vertices are assigned to multiple communities, and multiple assignment sequences are obtained, each assignment sequence includes multiple vertices, and vertex positions corresponding to each vertex;

Step S20: select a vertex position as the target position, and in each allocation sequence, compare the target vertex corresponding to the target position and the remaining vertices, and obtain a plurality of vertex similarities corresponding to each allocation sequence;

Step S30: determining an allocation strategy according to the similarity of multiple vertices;

Step S40: Obtain the probability of the allocation strategy according to the random allocation probability value and the allocation strategy of the plurality of vertices allocated to the plurality of communities.

In one embodiment, as shown in FIG. 2 , step S10 includes:

其中，N≥1，K≥1，i≥1，N＞K。Step S101: N vertices are allocated to K communities, i allocation sequences are obtained, the N vertices include x ₁ , x ₂ ...... x _N , and the i allocation sequences include:

Among them, N≥1, K≥1, i≥1, N>K.

In one embodiment, as shown in FIG. 2 , step S20 includes:

Step S201: select a vertex position as the target position g;

与剩余顶点，若相同，则赋值1，若不同，则赋值0，得到的顶点相似度为

其中，i个分配序列对应的i个顶点相似度包括：Y₁，Y₂...Y_i。Step S202: in the allocation sequence Xi, compare the target vertices corresponding to the target position _g

and the remaining vertices, if they are the same, assign 1, and if they are different, assign 0, and the obtained vertex similarity is

Wherein, the i vertex similarities corresponding to the i allocation sequences include: Y ₁ , Y ₂ . . . Y _i .

In one embodiment, as shown in FIG. 2 , step S30 includes:

i为奇数，分配策略X'_i是所述目标顶点与所述剩余顶点相同。S301: When there are multiple vertex similarities greater than or equal to a preset threshold, wherein the preset threshold is

i is an odd number, and the allocation strategy X' _i is that the target vertex is the same as the remaining vertex.

In one embodiment, as shown in FIG. 2 , step S30 includes:

S302: When there are multiple vertex similarities smaller than the preset threshold, the allocation strategy X' _i is to allocate adjacent vertices to K communities.

In one embodiment, as shown in FIG. 2 , step S30 includes:

i为奇数，分配策略X'_i是重新选择所述目标位置。S303: When there is only one vertex similarity greater than or equal to a preset threshold, wherein the preset threshold is

i is an odd number, and the allocation strategy X' _i is to reselect the target position.

In one embodiment, as shown in FIG. 2 , step S40 includes:

计算分配策略的概率，其中，多个顶点分配至多个社区的随机分配概率值为ε。Utilization

Calculate the probability of the assignment strategy, where the random assignment probability of multiple vertices to multiple communities is ε.

In one example, this embodiment proposes a strategy process for the reinforcement learning of vertices assigned to communities, and introduces the vertex assignment of genetic algorithm as a guide, so that the final vertex assignment to each community can converge to the optimal faster and better. untie.

之后，选择目标位置g，三个分配序列中，目标位置g对应的目标顶点包括：

每个分配序列中将目标顶点和剩余顶点进行比较。例如，在第一个分配序列中，分别比较

和

和

……

和

若相同，则赋值为1，若不同则赋值为0，得到第一个分配序列对应的第一顶点相似度Y₁。同理，在第二个分配序列中，分别比较

和

和

……

和

若相同，则赋值为1，若不同则赋值为0，得到第二个分配序列对应的第二顶点相似度Y₂。在第三个分配序列中，分别比较

和

和

……

和

若相同，则赋值为1，若不同则赋值为0，得到第三个分配序列对应的第三顶点相似度Y₃。将三个顶点相似度进行集合，可用

表示顶点相似度集合。之后，将Y与X₁进行如下的操作：X'₁＝Y∞X₁，∞可表示为：当Y中只有一个大于或等于预设阈值的顶点相似度时，将重新选择目标位置；当Y中有多个大于或等于预设阈值的顶点相似度时，三个分配序列中，目标位置对应的目标顶点相同，即

和

相同；当Y中有多个小于预设阈值的顶点相似度时，应当将与

和

邻接顶点分配至K个社区中。最终的X'₁为目标顶点

对K个社区的分布；同理，将Y与X₂进行如下的操作：X'₂＝Y∞X₂，最终的X'₂为目标顶点

对K个社区的分布，将Y与X₃进行如下的操作：X'₃＝Y∞X₃，最终的X'₃为目标顶点

对K个社区的分布。通过以上步骤能够得到遗传算法在当前状态给予的顶点对社区的分配的思想(过程对应于图7中的节点分配方案)，可以在强化学习的策略阶段引入该指导策略，最终可以在策略的ε-greedy贪婪算法采样阶段引入分配结果的指导，最终的顶点对社区的分配策略的概率(对应于图7中的社区结果)为：As shown in FIG. 7 , first, an odd number of assignment sequences (corresponding to the action sequence in FIG. 7 ) of the vertices (corresponding to the vertex code U in FIG. 7 ) to the community (corresponding to the community code in FIG. 7 ) are randomly obtained. Taking the acquisition of three allocation sequences as an example to illustrate, the _N vertices include x ₁ , x ₂ ...... include

After that, select the target position g. In the three allocation sequences, the target vertices corresponding to the target position g include:

The target vertex and the remaining vertices are compared in each allocation sequence. For example, in the first assignment sequence, compare

and

and

...

and

If they are the same, assign a value of 1, and if they are different, assign a value of 0 to obtain the first vertex similarity Y ₁ corresponding to the first assignment sequence. Similarly, in the second allocation sequence, compare

and

and

...

and

If they are the same, assign a value of 1, and if they are different, assign a value of 0 to obtain the second vertex similarity Y ₂ corresponding to the second assignment sequence. In the third assignment sequence, compare

and

and

...

and

If they are the same, assign a value of 1, and if they are different, assign a value of 0 to obtain the third vertex similarity Y ₃ corresponding to the third assignment sequence. Set the similarity of three vertices, available

Represents the vertex similarity set. After that, perform the following operations on Y and X ₁ : X' ₁ =Y∞X ₁ , ∞ can be expressed as: when there is only one vertex similarity greater than or equal to the preset threshold in Y, the target position will be reselected; when When there are multiple vertex similarities greater than or equal to the preset threshold in Y, in the three assignment sequences, the target vertices corresponding to the target positions are the same, that is,

and

The same; when there are multiple vertex similarities less than the preset threshold in Y, it should be compared with

and

Adjacent vertices are assigned to K communities. The final X' ₁ is the target vertex

The distribution of K communities; similarly, perform the following operations on Y and X ₂ : X' ₂ =Y∞X ₂ , the final X' ₂ is the target vertex

For the distribution of K communities, perform the following operations on Y and X ₃ : X' ₃ =Y∞X ₃ , the final X' ₃ is the target vertex

Distribution over K communities. Through the above steps, the idea of assigning the vertices to the community given by the genetic algorithm in the current state can be obtained (the process corresponds to the node assignment scheme in Figure 7). -The greedy algorithm sampling phase introduces the guidance of the distribution result, and the probability of the final vertex-to-community distribution strategy (corresponding to the community result in Figure 7) is:

其中，A_i为社区的分配策略的概率,多个顶点分配至多个社区的随机分配概率值为ε。

Among them, A _i is the probability of the distribution strategy of the community, and the random distribution probability of multiple vertices assigned to multiple communities is ε.

The allocation method provided in this embodiment is better and more optimal for the allocation of vertices to the community, and can better converge to the optimal allocation result compared with the traditional strategy. The distribution method provided in this embodiment is also applicable to recommendation problems, such as product recommendation, where items are distributed to different groups of people. The assignment method provided in this embodiment is also applicable to classification and clustering problems, for example, the social product is to directly discover its crowd.

The following are the convergence and convergence effects of the final objective of the strategy of adding a multiobjective evolutionary algorithm (MOEA, a multiobjective evolutionary algorithm) and the traditional non-MOEA ε-greedy process on four datasets. As shown in Figure 3, the strategy of joining MOEA and the distribution curve of the non-MOEA algorithm for the Cornell community dataset are shown in Figure 3. The strategy for joining MOEA and the non-MOEA algorithm for the Cornell community dataset are shown in Figure 3. The allocation curve of the algorithm is shown in Figure 4. The strategy of joining MOEA in the political blog dataset Polblogs Dataset and the allocation curve of the non-MOEA algorithm are shown in Figure 5. The strategy of joining MOEA in the Washington community data set and Distribution plot for the non-MOEA algorithm. As shown in Figure 6, the strategy of joining MOEA and the distribution curve of the non-MOEA algorithm for the Wisconsin community dataset in Wisconsin. It can be seen from the above four data graphs that the strategy of adding MOEA has better convergence than the non-MOEA algorithm and achieves a better T target.

FIG. 8 shows a structural block diagram of an apparatus for allocating vertices to communities according to an embodiment of the present invention. As shown in Figure 8, in one embodiment, the device includes:

The allocation sequence acquisition module 10 is used to allocate a plurality of vertices to a plurality of communities to obtain a plurality of allocation sequences, and each of the allocation sequences includes a plurality of the vertices and a vertex position corresponding to each of the vertices;

The vertex similarity calculation module 20 is used to select a vertex position as the target position, and in each of the allocation sequences, compare the target vertex corresponding to the target position with the remaining vertices, and obtain a plurality of vertices corresponding to each of the allocation sequences that are similar Spend;

an allocation strategy determination module 30, configured to determine an allocation strategy according to a plurality of the vertex similarities;

The allocation strategy probability calculation module 40 is configured to obtain the probability of the allocation strategy according to the random allocation probability values of the plurality of vertices allocated to the plurality of communities and the allocation strategy.

In one embodiment, as shown in FIG. 9 , the allocation sequence acquisition module 10 includes:

其中，N≥1，K≥1，i≥1，N＞K。The allocation unit 101 is used for allocating N vertices to K communities to obtain i allocation sequences, the N vertices include x ₁ , x ₂ ...... x _N , and the i allocation sequences include:

Among them, N≥1, K≥1, i≥1, N>K.

In one embodiment, as shown in FIG. 9 , the vertex similarity calculation module 20 includes:

a target position selection unit 201 for selecting a vertex position as the target position g;

与剩余顶点，得到的顶点相似度为

其中，i个分配序列对应的i个顶点相似度包括：Y₁，Y₂...Y_i。The similarity calculation unit 202 is used to compare the target vertices corresponding to the target position g in the allocation sequence X _i

With the remaining vertices, the obtained vertex similarity is

Wherein, the i vertex similarities corresponding to the i allocation sequences include: Y ₁ , Y ₂ . . . Y _i .

In one embodiment, as shown in FIG. 9 , the allocation strategy determination module 30 includes:

i为奇数，分配策略X'_i是i个分配序列中对应的目标顶点相同。The first allocation strategy unit 301 is used when there are multiple vertex similarities greater than or equal to a preset threshold, wherein the preset threshold is

i is an odd number, and the allocation strategy X' _i is that the corresponding target vertices in the i allocation sequences are the same.

In one embodiment, as shown in FIG. 9 , the allocation strategy determination module 30 includes:

The second allocation strategy unit 302 is configured to allocate adjacent vertices to K communities when there are multiple vertex similarities smaller than the preset threshold, the allocation strategy X' _i .

In one embodiment, as shown in FIG. 9 , the allocation strategy determination module 30 includes:

i为奇数，分配策略X'_i是重新选择所述目标位置。The third allocation strategy unit 303 is used for when there is only one vertex similarity greater than or equal to a preset threshold, wherein the preset threshold is

i is an odd number, and the allocation strategy X' _i is to reselect the target position.

In one embodiment, as shown in FIG. 9 , the distribution strategy probability calculation module 40 includes:

计算分配策略的概率，其中，多个顶点分配至多个社区的随机分配概率值为ε。Probability calculation unit 401 for using the formula

Calculate the probability of the assignment strategy, where the random assignment probability of multiple vertices to multiple communities is ε.

For the functions of each module in each apparatus in this embodiment of the present invention, reference may be made to the corresponding description in the foregoing method, and details are not described herein again.

FIG. 10 shows a structural block diagram of a terminal for assigning vertices to communities according to an embodiment of the present invention. As shown in FIG. 10 , the terminal includes: a memory 910 and a processor 920 , and a computer program that can be executed on the processor 920 is stored in the memory 910 . When the processor 920 executes the computer program, the method for allocating vertices to communities in the above embodiments is implemented. The number of the memory 910 and the processor 920 may be one or more.

The terminal also includes:

The communication interface 930 is used to communicate with external devices and perform data interactive transmission.

The memory 910 may include high-speed RAM memory, and may also include non-volatile memory, such as at least one disk memory.

If the memory 910, the processor 920 and the communication interface 930 are independently implemented, the memory 910, the processor 920 and the communication interface 930 may be connected to each other through a bus and complete communication with each other. The bus may be an Industry Standard Architecture (ISA, Industry Standard Architecture) bus, a Peripheral Component Interconnect (PCI, Peripheral Component Interconnect) bus, or an Extended Industry Standard Architecture (EISA, Extended Industry Standard Architecture) bus or the like. The bus can be divided into an address bus, a data bus, a control bus, and the like. For ease of presentation, only one thick line is used in FIG. 10, but it does not mean that there is only one bus or one type of bus.

Optionally, in specific implementation, if the memory 910, the processor 920 and the communication interface 930 are integrated on one chip, the memory 910, the processor 920 and the communication interface 930 can communicate with each other through an internal interface.

An embodiment of the present invention provides a computer-readable storage medium, which stores a computer program, and when the program is executed by a processor, implements any of the methods described in the foregoing embodiments.

In the description of this specification, description with reference to the terms "one embodiment," "some embodiments," "example," "specific example," or "some examples", etc., mean specific features described in connection with the embodiment or example , structure, material or feature is included in at least one embodiment or example of the present invention. Furthermore, the particular features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, those skilled in the art may combine and combine the different embodiments or examples described in this specification, as well as the features of the different embodiments or examples, without conflicting each other.

In addition, the terms "first" and "second" are only used for descriptive purposes, and should not be construed as indicating or implying relative importance or implying the number of indicated technical features. Thus, a feature delimited with "first", "second" may expressly or implicitly include at least one of that feature. In the description of the present invention, "plurality" means two or more, unless otherwise expressly and specifically defined.

Any description of a process or method in the flowcharts or otherwise described herein may be understood to represent a module, segment or portion of code comprising one or more executable instructions for implementing a specified logical function or step of the process , and the scope of the preferred embodiments of the invention includes alternative implementations in which the functions may be performed out of the order shown or discussed, including performing the functions substantially concurrently or in the reverse order depending upon the functions involved, which should It is understood by those skilled in the art to which the embodiments of the present invention belong.

The logic and/or steps represented in flowcharts or otherwise described herein, for example, may be considered an ordered listing of executable instructions for implementing the logical functions, may be embodied in any computer-readable medium, For use with, or in conjunction with, an instruction execution system, apparatus, or device (such as a computer-based system, a system including a processor, or other system that can fetch instructions from and execute instructions from an instruction execution system, apparatus, or apparatus) or equipment. For the purposes of this specification, a "computer-readable medium" can be any device that can contain, store, communicate, propagate, or transport the program for use by or in connection with an instruction execution system, apparatus, or apparatus. More specific examples (non-exhaustive list) of computer readable media include the following: electrical connections with one or more wiring (electronic devices), portable computer disk cartridges (magnetic devices), random access memory (RAM), Read Only Memory (ROM), Erasable Editable Read Only Memory (EPROM or Flash Memory), Fiber Optic Devices, and Portable Read Only Memory (CDROM). In addition, the computer readable medium may even be paper or other suitable medium on which the program may be printed, as the paper or other medium may be optically scanned, for example, followed by editing, interpretation, or other suitable medium as necessary process to obtain the program electronically and then store it in computer memory.

It should be understood that various parts of the present invention may be implemented in hardware, software, firmware or a combination thereof. In the above-described embodiments, various steps or methods may be implemented in software or firmware stored in memory and executed by a suitable instruction execution system. For example, if implemented in hardware, as in another embodiment, it can be implemented by any one or a combination of the following techniques known in the art: Discrete logic circuits, application specific integrated circuits with suitable combinational logic gates, Programmable Gate Arrays (PGA), Field Programmable Gate Arrays (FPGA), etc.

Those skilled in the art can understand that all or part of the steps carried by the methods of the above embodiments can be completed by instructing the relevant hardware through a program, and the program can be stored in a computer-readable storage medium, and the program can be stored in a computer-readable storage medium. When executed, one or a combination of the steps of the method embodiment is included.

In addition, each functional unit in each embodiment of the present invention may be integrated into one processing module, or each unit may exist physically alone, or two or more units may be integrated into one module. The above-mentioned integrated modules can be implemented in the form of hardware, and can also be implemented in the form of software function modules. If the integrated modules are implemented in the form of software functional modules and sold or used as independent products, they may also be stored in a computer-readable storage medium. The storage medium may be a read-only memory, a magnetic disk or an optical disk, and the like.

The above are only specific embodiments of the present invention, but the protection scope of the present invention is not limited to this. Any person skilled in the art who is familiar with the technical field disclosed in the present invention can easily think of various changes or Replacement, these should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope of the claims.

Claims (16)

1. A vertex-to-community allocation method, comprising:

distributing a plurality of vertexes to a plurality of communities to obtain a plurality of distribution sequences, wherein each distribution sequence comprises a plurality of vertexes and vertex positions corresponding to the vertexes;

selecting a vertex position as a target position, and comparing a target vertex corresponding to the target position with the rest of vertices in each distribution sequence to obtain a plurality of vertex similarities corresponding to each distribution sequence;

determining an allocation strategy according to the similarity of the vertexes;

and obtaining the probability of the distribution strategy according to the random distribution probability value and the distribution strategy of the plurality of vertexes distributed to the plurality of communities.

2. The method of claim 1, wherein assigning vertices to communities results in a plurality of sets of assigned sequences, comprising:

distributing N vertexes to K communities to obtain i distribution sequences, wherein the N vertexes comprise x₁、x₂……x_NThe i allocation sequences include:

wherein N is more than or equal to 1, K is more than or equal to 1, i is more than or equal to 1, and N is more than K.

3. The method of claim 2, wherein selecting a vertex position as a target position, and in each of the distribution sequences, comparing the target vertex corresponding to the target position with the remaining vertices to obtain a plurality of vertex similarities corresponding to each of the distribution sequences comprises:

selecting a vertex position as a target position g;

in the distribution sequence X_iIn (1), comparing the target vertex corresponding to the target position g

With the remaining vertices, the resulting vertex similarity is

Wherein, i vertex similarities corresponding to the i distribution sequences include: y is₁，Y₂...Y_i。

4. The method of claim 3, wherein determining an allocation policy based on the plurality of vertex similarities comprises:

when the vertex similarity greater than or equal to a preset threshold value is multiple, wherein the preset threshold value is

i is odd, strategy X 'is assigned'_iThe corresponding target vertices in the i assignment sequences are the same.

5. The method of claim 3, wherein determining an allocation policy based on the plurality of vertex similarities comprises:

when the vertex similarity smaller than the preset threshold value is multiple, distributing strategy X'_iContiguous vertices are assigned to K communities.

6. The method of claim 3, wherein determining an allocation policy based on the plurality of vertex similarities comprises:

when the vertex similarity greater than or equal to a preset threshold value is only one, wherein the preset threshold value is

i is odd, strategy X 'is assigned'_iIs to reselect the target location.

7. The method of any one of claims 4-6, wherein deriving the probability of the allocation policy based on the random allocation probability values of the vertices to the communities and the allocation policy comprises:

by using

And calculating the probability of the distribution strategy, wherein the random distribution probability values of the plurality of vertexes distributed to the plurality of communities are.

8. An apparatus for vertex-to-community assignment, comprising:

the distribution sequence acquisition module is used for distributing a plurality of vertexes to a plurality of communities to obtain a plurality of distribution sequences, and each distribution sequence comprises a plurality of vertexes and vertex positions corresponding to the vertexes;

the vertex similarity calculation module is used for selecting a vertex position as a target position, and comparing a target vertex corresponding to the target position with the rest of vertices in each distribution sequence to obtain a plurality of vertex similarities corresponding to each distribution sequence;

the distribution strategy determining module is used for determining a distribution strategy according to the similarity of the vertexes;

and the distribution strategy probability calculation module is used for obtaining the probability of the distribution strategy according to the random distribution probability values distributed to the communities by the vertexes and the distribution strategy.

9. The apparatus of claim 8, wherein the allocation sequence obtaining module comprises:

an allocation unit for allocating N vertexes to K communities to obtain i allocation sequences, wherein the N vertexes include x₁、x₂……x_NThe i allocation sequences include:

wherein N is more than or equal to 1, K is more than or equal to 1, i is more than or equal to 1, and N is more than K.

10. The apparatus of claim 9, wherein the vertex similarity calculation module comprises:

a target position selection unit for selecting a vertex position as a target position g;

a similarity calculation unit for calculating a similarity between the assigned sequence X and the assigned sequence X_iIn (1), comparing the target position g withTarget vertex

With the remaining vertices, the resulting vertex similarity is

The similarity set unit is used for i vertex similarities corresponding to the i distribution sequences and comprises the following steps: y is₁，Y₂...Y_i。

11. The apparatus of claim 10, wherein the allocation policy determination module comprises:

a first allocation strategy unit, configured to apply to a case where there are multiple vertex similarities greater than or equal to a preset threshold, where the preset threshold is

i is odd, strategy X 'is assigned'_iThe corresponding target vertices in the i assignment sequences are the same.

12. The apparatus of claim 10, wherein the allocation policy determination module comprises:

a second distribution strategy unit for distributing strategy X 'when there are more vertex similarities less than the preset threshold'_iContiguous vertices are assigned to K communities.

13. The apparatus of claim 10, wherein the allocation policy determination module comprises:

a third allocation policy unit, configured to, when there is only one vertex similarity greater than or equal to a preset threshold, where the preset threshold is

i is odd, strategy X 'is assigned'_iIs to reselect the target location.

14. The apparatus according to any of claims 10-13, wherein the allocation policy probability calculation module comprises:

probability calculation unit for using

And calculating the probability of the distribution strategy, wherein the random distribution probability values of the plurality of vertexes distributed to the plurality of communities are.

15. A vertex-to-community distribution terminal, comprising:

one or more processors;

storage means for storing one or more programs;

the one or more programs, when executed by the one or more processors, cause the one or more processors to implement the method of any of claims 1-7.

16. A computer-readable storage medium, in which a computer program is stored which, when being executed by a processor, carries out the method according to any one of claims 1 to 7.

Images