CN108712278A - A kind of network community discovery method based on integrated study - Google Patents
A kind of network community discovery method based on integrated study Download PDFInfo
- Publication number
- CN108712278A CN108712278A CN201810373662.1A CN201810373662A CN108712278A CN 108712278 A CN108712278 A CN 108712278A CN 201810373662 A CN201810373662 A CN 201810373662A CN 108712278 A CN108712278 A CN 108712278A
- Authority
- CN
- China
- Prior art keywords
- network
- community
- nodes
- discovery
- independent
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 46
- 239000011159 matrix material Substances 0.000 claims abstract description 29
- 230000010354 integration Effects 0.000 claims description 9
- 238000004364 calculation method Methods 0.000 claims description 8
- 230000000087 stabilizing effect Effects 0.000 claims description 2
- 238000004422 calculation algorithm Methods 0.000 abstract description 24
- 238000013441 quality evaluation Methods 0.000 abstract 1
- 230000007547 defect Effects 0.000 description 3
- 230000000644 propagated effect Effects 0.000 description 3
- 238000010586 diagram Methods 0.000 description 2
- 238000007500 overflow downdraw method Methods 0.000 description 2
- 238000005295 random walk Methods 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000004590 computer program Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000007418 data mining Methods 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000009826 distribution Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 238000012804 iterative process Methods 0.000 description 1
- 238000002372 labelling Methods 0.000 description 1
- 238000013507 mapping Methods 0.000 description 1
- 238000003012 network analysis Methods 0.000 description 1
- 230000008520 organization Effects 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/08—Configuration management of networks or network elements
- H04L41/0803—Configuration setting
- H04L41/0813—Configuration setting characterised by the conditions triggering a change of settings
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/08—Configuration management of networks or network elements
- H04L41/0803—Configuration setting
- H04L41/0823—Configuration setting characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/12—Discovery or management of network topologies
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L43/00—Arrangements for monitoring or testing data switching networks
- H04L43/08—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
- H04L43/091—Measuring contribution of individual network components to actual service level
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Environmental & Geological Engineering (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
A kind of network community discovery method based on integrated study of the present invention, belongs to Complex Networks Analysis technical field；For solving pinpointing the problems for community structure in complex network；The present invention key step include：Multiple label propagation algorithm is independently repeated to network first, generate multiple mutually independent community discovery results, quality evaluation is carried out to these independent community discovery results respectively followed by modularity index, and its importance weight is calculated with this, then independent community discovery result is weighted integrated, the integrated discovery of the Web Community with more high stability and robustness is obtained as a result, finally carrying out result output by calculating integrated relationship matrix；That present invention preserves label propagation algorithms is simple in structure, is easily achieved, and the advantage that time complexity is relatively low, the shortcomings that overcoming strong label propagation algorithm randomness, poor reliability using integrated learning approach simultaneously, the Web Community that can obtain high stability find result.
Description
Technical Field
The invention relates to the field of complex network analysis, in particular to a network community discovery method based on ensemble learning.
Background
With the push of information technology, complex networks represented by social networks, traffic networks, biological networks, Web networks, communication networks, and the like have become an important part constituting and affecting our lives. Research on complex networks has also become a hotspot across many disciplines, such as computer, physics, mathematics, sociology, biology, etc., and has received widespread attention from both academic and industrial circles. The community structure is a mapping of the relationships among entities in the real world as the most ubiquitous and important topological attribute of a complex network. The process of discovering the community structure and the community to which each node belongs in a complex network by using the topology structure of the network and the information of the nodes through a specific effective algorithm is called community discovery. The research work of community discovery has many realistic meanings, and can help people to know rich contents in the network, understand the development rules of the organization structure of the network community, the mutual relation of the topological structures and the like. In recent years, a large number of representative methods have been formed for the community discovery problem of the complex network, wherein the label propagation algorithm is widely applied to the community structure discovery of the complex network due to the advantages of simple algorithm implementation and low computational complexity. The method includes the steps that firstly, community labels are randomly distributed to all nodes in a network, each node updates own label according to the labels of neighbor nodes in the node propagation process, the greater the similarity with the node is, the greater the influence weight value of the neighbor nodes on labeling of the neighbor nodes is, the more the labels of the similar nodes tend to be consistent, and the easier the labels are propagated. Finally, when the iterative process is finished, the probability distributions of the similar nodes tend to be similar, and the similar nodes can be divided into the same category, so that the label propagation process is completed.
However, in practical applications, the label propagation algorithm has a large randomness in the initial label, the node selection and the updating sequence, so that the community discovery result is not stable enough, and sometimes a singular solution is generated, that is, all nodes have the same label. Therefore, how to fully exert the advantage of low time complexity of the label propagation algorithm and enhance the robustness of the community discovery result is of great significance for further improving the performance of the algorithm and expanding the application range of the algorithm.
Patent publication No. CN106886524A, namely a social network community division method based on random walk, solves the problem of excessive randomness of the traditional label algorithm in the label updating process. Firstly, introducing a random walk idea, and calculating to obtain a matrix for measuring similarity between network nodes; secondly, in the label propagation process, when the appearance frequency of labels in the neighbor nodes is multiple highest, the labels owned by the neighbor nodes with the highest similarity are selected to be updated instead of being randomly selected, so that the labels are prevented from being propagated randomly among communities; finally, a real network and an artificial reference network are used for testing, and the result shows that the algorithm obtains better performance than the original algorithm in community discovery. Patent CN105631748A discloses a heterogeneous network community discovery method based on parallel label propagation, which comprises a label initialization stage, a label cycle updating stage and a community construction stage; the label circulation updating phase is based on parallel label propagation, allows the node labels to be relatively independently propagated in parallel in a plurality of sub-networks of the heterogeneous network, and updates the node labels by fusing parallel propagation results of the plurality of sub-networks. Compared with a linear fusion method, namely Linear Command, the fusion method based on parallel label propagation can more effectively utilize heterogeneous interaction information among nodes and is more suitable for heterogeneous network community discovery. A patent 'parallel overlapping community discovery method based on label propagation under Spark' with publication number CN106991614A provides a parallel community discovery method based on label propagation under Spark, and relates to the field of data mining. The invention searches a complete subgraph in the network and assigns the same label to the nodes in the complete subgraph, thereby reducing the defect of excessive labels in the initialization stage and improving the execution efficiency of the algorithm; secondly, calculating the propagation probability of the nodes in the network according to the weight of the nodes, and comprehensively considering the propagation probability of the labels and the similarity among the nodes in the label selection stage, thereby improving the accuracy of the label selection stage; the whole algorithm is executed under a Spark framework, good expandability is achieved for mass data, and the execution efficiency and the community discovery accuracy are obviously improved. However, none of the above disclosures solves the problems of strong randomness of the label propagation method and unstable community discovery results.
Disclosure of Invention
The invention discloses a network community discovery method based on ensemble learning, overcomes the defects in the prior art, and provides a network community discovery method for improving the robustness of a network community discovery result of a label propagation algorithm.
In order to solve the technical problems, the invention adopts the technical scheme that: a network community discovery method based on ensemble learning utilizes G (V, E) to represent a network, wherein V ═ V (V, E)1,v2,…,vm) Representing a set of nodes in the network, the ith network node (1 ≦ i ≦ m) denoted vi；E＝(e1,e2,…,en) Representing a set of nodes connecting edges in the network, wherein the jth edge (j is more than or equal to 1 and less than or equal to n) is marked as ej；L＝(l1,l2,…,ln) Set of labels representing all nodes in the network, i-th network node viThe community label of is noted as liDenotes the ith network node viBelong toiRepresentative communities, K denotes the number of communities included in the network, liIs taken asi1,2, …, K, comprising the steps of:
s10, initializing a community tag of each network node in the network G (V, E), wherein each community tag has a unique initialization value;
s20, carrying out propagation updating on community labels of the network nodes in sequence according to the node arrangement sequence in the node set of the network G (V, E), and after multiple iterations, stabilizing the community labels of the nodes to obtain a group of network community discovery results, namely a set formed by the community labels of all the nodes in the network;
s30, independently and repeatedly executing the S10 and the S20M times on the network G (V, E), and respectively obtaining M groups of mutually independent network community discovery results (hereinafter referred to as independent discovery results);
s40, calculating the community structure modularity of the M groups of independent discovery results obtained in the S30 respectively, and evaluating the quality of each group of independent discovery results;
s50, calculating importance weights of the community structure by using the community structure modularity of each group of independent discovery results;
and S60, performing weighted integration on each group of independent discovery results to obtain network community integrated discovery results with higher stability and robustness, and outputting the results.
Further, the community label l in the step S10iThe values of (b) are randomly generated from the set {1,2, …, K }, that is, in an initialization state, each node of the network G (V, E) is randomly distributed to K network communities.
Further, the step S20 includes the steps of:
s21, according to the arrangement sequence of the network nodes, the 1 st network node V in the network G (V, E)1From the beginning, to the m network node vmPropagating and updating the community label of each network node in sequence, and any network node V in the network G (V, E)iCommunity label liIs determined by the community label of its neighbor nodes, i.e. v is selectediIf a plurality of community label values which occur most exist in the neighbor nodes of a certain network node, one of the community label values is randomly selected as an updated value;
and S22, continuously iterating and executing S21 until community label values of all network nodes in the network G (V, E) are not changed any more, and taking an assembly formed by the community labels of all the network nodes at the moment as a group of network community discovery results.
Further, the method for calculating the community structure modularity of the M groups of independent discovery results in step S40 is as shown in formula (1):
wherein Q isoIs the o group independent community discovery result LoThe community structure modularity of (1); p, q denote the order of any two network nodes in the network G (V, E)Number, p is more than or equal to 1, q is not equal to or less than m; a is an adjacent matrix of the network G (V, E), the elements A of whichpqThe value is 0 or 1, which represents the network node V in the network G (V, E)pAnd vqThe number of connecting edges between;andrespectively representing network nodes vpAnd vqDegree of (d); lpAnd lqAre respectively network nodes vpAnd vqIf node vpAnd vqIf they belong to a network community, then δ (l)p,lq) 1, otherwise δ (l)p,lq)＝0。
Further, the method for calculating the importance weight by using the community structure modularity of each group of independent discovery results in step S50 is as shown in formula (2):
wherein, ω isoAn importance weight representing the no group independent discovery result,the calculation method is the sum of the community structure modularity of the M groups of independent discovery results, and is shown as the formula (3):
further, the step S60 includes the steps of:
s61, calculating an integrated relation matrix by using M groups of independent discovery results and corresponding importance weights, wherein the integrated relation matrix is marked as S, the scale of the integrated relation matrix is M multiplied by M, the integrated relation matrix is determined by the number of network nodes in the network G (V, E), and the matrix element S of the integrated relation matrix isα,βThe calculation method of (2) is shown in formula (4):
wherein,andrespectively representing network nodes v in the o-th group independent discovery resultαAnd vβThe community tag of (1), ifThenOtherwise
S62, for any element S in the integrated relation matrixα,βIf S isα,βIf > 0.5, the network node v is connectedαAnd vβBelonging to the same network community; if Sα,βIf the value is less than or equal to 0.5, the network node v is considered to be the network node vαAnd vβAnd finally, outputting the community label of each network node as a final result of the network community discovery method.
Compared with the prior art, the invention has the beneficial effects that: the method provided by the invention reserves the advantages of simple structure, easy realization and low time complexity of the label propagation algorithm, overcomes the defects of strong randomness and poor reliability of the label propagation algorithm by using the integrated learning method, and can obtain a network community discovery result with high stability. In addition, the generation of a plurality of independent community discovery results and the community structure modularity calculation process are suitable for parallel implementation of computers, and higher calculation efficiency can be obtained.
Drawings
Fig. 1 is a computer implemented system structure diagram of a web community discovery method based on ensemble learning according to the present invention.
Fig. 2 is a flowchart illustrating an implementation of the web community discovery method based on ensemble learning according to the present invention.
Detailed Description
The following detailed description of embodiments of the invention refers to the accompanying drawings.
The invention relates to a network community discovery method based on ensemble learning, which is implemented by a computer program, as shown in figure 1, in a structure diagram of a computer implementation system, a network data storage unit is used for storing nodes of a network to be processed and the connection relation between the nodes; the label propagation algorithm unit is used for generating a plurality of groups of independent network community discovery results through a label propagation algorithm; the independent community discovery result evaluation unit is used for evaluating the quality of each group of results; the community discovery result integration unit is used for performing weighted integration on the independent community discovery results so as to generate network community discovery results with higher stability and reliability; the computer processor and the memory are physical entities for the above units to complete the operations and storage. The following describes the detailed implementation of the technical solution proposed by the present invention according to the flow chart shown in fig. 2.
A network community discovery method based on ensemble learning is a process of determining final values of network node community labels in a network G (V, E) through iterative computation, and G (V, E) is used for representing a network, wherein V ═ V (V, E)1,v2,…,vm) Representing a set of nodes in the network, the ith network node (1 ≦ i ≦ m) denoted vi；E＝(e1,e2,…,en) Representing a set of nodes connecting edges in the network, wherein the jth edge (j is more than or equal to 1 and less than or equal to n) is marked as ej；L＝(l1,l2,…,ln) Set of labels representing all nodes in the network, i-th network node viThe community label of is noted as liDenotes the ith network node viBelong toiRepresentative communities, K denotes the number of communities included in the network, liIs taken asi1,2, …, K, comprising the steps of:
s10, initializing a community tag of each network node in the network G (V, E), wherein each community tag has a unique initialization value;
community label liThe values of (b) are randomly generated from the set {1,2, …, K }, that is, in an initialization state, each node of the network G (V, E) is randomly distributed to K network communities.
S21, according to the arrangement sequence of the network nodes, the 1 st network node V in the network G (V, E)1From the beginning, to the m network node vmPropagating and updating the community label of each network node in sequence, and any network node V in the network G (V, E)iCommunity label liIs determined by the community label of its neighbor nodes, i.e. v is selectediIf a plurality of community label values which occur most exist in the neighbor nodes of a certain network node, one of the community label values is randomly selected as an updated value;
and S22, continuously iterating and executing S21 until community label values of all network nodes in the network G (V, E) are not changed any more, and taking an assembly formed by the community labels of all the network nodes at the moment as a group of network community discovery results. I.e. a set of community tags for all nodes in the network;
s30, independently and repeatedly executing the S10 and the S20M times on the network G (V, E), and respectively obtaining M groups of mutually independent network community discovery results (hereinafter referred to as independent discovery results); independent finding result, recorded as Φ ═ LoAnd (c) the step of (c) in which,the value of o is 1,2, …, and M is the integration scale of the algorithm, the ith network node v in the o group independent discovery result is showniIs recorded as a community tag
The independent and repeated execution of the M times of S10 and S20 on the network G (V, E) in S30 means that random initialization of the community tags of the network nodes in the network G (V, E) is independent and does not affect each other when the S10 is executed any two times, and the propagation updating processes of the community tags of the network nodes in the network G (V, E) are also independent and does not affect each other when the S20 is executed any two times, so that it is ensured that the M-group network community discovery results obtained by independently and repeatedly executing the M times of S10 and S20 on the network G (V, E) are independent from each other.
S40, calculating the community structure modularity of the M groups of independent discovery results obtained in the S30 respectively, and evaluating the quality of each group of independent discovery results; the method for respectively calculating the community structure modularity of the M groups of independent discovery results is shown as the formula (1):
wherein Q isoIs the o group independent community discovery result LoThe community structure modularity of (1); p and q represent the serial numbers of any two network nodes in the network G (V, E), and p is more than or equal to 1 and is not equal to q and is not more than m; a is an adjacent matrix of the network G (V, E), the elements A of whichpqThe value is 0 or 1, which represents the network node V in the network G (V, E)pAnd vqThe number of connecting edges between;andrespectively representing network nodes vpAnd vqDegree of (d); lpAnd lqAre respectively network nodes vpAnd vqIf node vpAnd vqIf they belong to a network community, then δ (l)p,lq) 1, otherwise δ (l)p,lq)＝0。
S50, calculating importance weights of the community structure by using the community structure modularity of each group of independent discovery results; the method for calculating the importance weight by using the community structure modularity of each group of independent discovery results is shown as the formula (2):
wherein, ω isoAn importance weight representing the no group independent discovery result,the calculation method is the sum of the community structure modularity of the M groups of independent discovery results, and is shown as the formula (3):
s61, calculating an integrated relation matrix by using M groups of independent discovery results and corresponding importance weights, wherein the integrated relation matrix is marked as S, the scale of the integrated relation matrix is M multiplied by M, the integrated relation matrix is determined by the number of network nodes in the network G (V, E), and the matrix element S of the integrated relation matrix isα,βThe calculation method of (2) is shown in formula (4):
wherein,andeach representing the o-th group independentlyNetwork node v in discovery resultαAnd vβThe community tag of (1), ifThenOtherwise
S62, for any element S in the integrated relation matrixα,βIf S isα,βIf > 0.5, the network node v is connectedαAnd vβBelonging to the same network community; if Sα,βIf the value is less than or equal to 0.5, the network node v is considered to be the network node vαAnd vβThe network nodes in the network G (V, E) can be distributed to corresponding network communities by judging each element in the integrated relationship matrix, and finally, community labels of the network nodes are output to serve as final results of the network community discovery method.
The invention provides a network community discovery method based on integrated learning, aiming at the problems of strong randomness, poor community discovery result stability and the like of a label propagation algorithm during network community discovery. The main parameters of the invention include: the method comprises the following steps of network node serial number, network node community labels, algorithm integration scale, community structure modularity, independent community discovery result importance weight, integration relation matrix and the like. The network node sequence number is a network node arrangement sequence formed when the network is stored or recorded, and the label propagation updating is carried out according to the sequence; the network node community label is used for representing the number of the community structure to which the network node belongs; the algorithm integration scale is used for determining the number of independent community discovery results; the community structure modularity is used for evaluating the quality of community discovery results; the importance weight of the independent community discovery result is used for distributing the proportion of the result in the integration process; the integrated relationship matrix is used for generating a consistent integrated result from a plurality of independent community discovery results.
While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims.
Claims (6)
1. A network community discovery method based on ensemble learning utilizes G (V, E) to represent a network, wherein V ═ V (V, E)1,v2,…,vm) Representing a set of nodes in the network, the ith network node (1 ≦ i ≦ m) denoted vi；E＝(e1,e2,…,en) Representing a set of nodes connecting edges in the network, wherein the jth edge (j is more than or equal to 1 and less than or equal to n) is marked as ej；L＝(l1,l2,…,ln) Set of labels representing all nodes in the network, i-th network node viThe community label of is noted as liIs shown byIth network node viBelong toiRepresentative communities, K denotes the number of communities included in the network, liIs taken asi1,2, …, K, characterized by comprising the steps of:
s10, initializing a community tag of each network node in the network G (V, E), wherein each community tag has a unique initialization value;
s20, carrying out propagation updating on community labels of the network nodes in sequence according to the node arrangement sequence in the node set of the network G (V, E), and after multiple iterations, stabilizing the community labels of the nodes to obtain a group of network community discovery results, namely a set formed by the community labels of all the nodes in the network;
s30, independently and repeatedly executing the S10 and the S20M times on the network G (V, E), and respectively obtaining M groups of mutually independent network community discovery results (hereinafter referred to as independent discovery results);
s40, calculating the community structure modularity of the M groups of independent discovery results obtained in the S30 respectively, and evaluating the quality of each group of independent discovery results;
s50, calculating importance weights of the community structure by using the community structure modularity of each group of independent discovery results;
and S60, performing weighted integration on each group of independent discovery results to obtain network community integrated discovery results with higher stability and robustness, and outputting the results.
2. The ensemble learning-based web community discovery method according to claim 1, wherein the community label l in step S10iThe values of (b) are randomly generated from the set {1,2, …, K }, that is, in an initialization state, each node of the network G (V, E) is randomly distributed to K network communities.
3. The ensemble learning-based web community discovery method according to claim 1, wherein the step S20 comprises the following steps:
s21, according to the arrangement sequence of the network nodes, the 1 st network node V in the network G (V, E)1From the beginning, to the m network node vmPropagating and updating the community label of each network node in sequence, and any network node V in the network G (V, E)iCommunity label liIs determined by the community label of its neighbor nodes, i.e. v is selectediIf a plurality of community label values which occur most exist in the neighbor nodes of a certain network node, one of the community label values is randomly selected as an updated value;
and S22, continuously iterating and executing S21 until community label values of all network nodes in the network G (V, E) are not changed any more, and taking an assembly formed by the community labels of all the network nodes at the moment as a group of network community discovery results.
4. The method for discovering web community based on ensemble learning as claimed in claim 1, wherein the method for calculating community structure modularity for M groups of independent discovery results in step S40 is as shown in formula (1):
wherein Q isoIs the o group independent community discovery result LoThe community structure modularity of (1); p and q represent the serial numbers of any two network nodes in the network G (V, E), and p is more than or equal to 1 and is not equal to q and is not more than m; a is an adjacent matrix of the network G (V, E), the elements A of whichpqThe value is 0 or 1, which represents the network node V in the network G (V, E)pAnd vqThe number of connecting edges between;andrespectively representing network nodes vpAnd vqDegree of (d); lpAnd lqAre respectively network nodes vpAnd vqIf node vpAnd vqBelong to the same thingNetwork community, then δ (l)p,lq) 1, otherwise δ (l)p,lq)＝0。
5. The method for discovering web community based on ensemble learning according to claim 1, wherein the method for calculating importance weight of each group of independent discovery results in step S50 by using community structure modularity of each group of independent discovery results is as shown in formula (2):
wherein, ω isoAn importance weight representing the no group independent discovery result,the calculation method is the sum of the community structure modularity of the M groups of independent discovery results, and is shown as the formula (3):
6. the ensemble learning-based web community discovery method according to claim 1, wherein the step S60 comprises the following steps:
s61, calculating an integrated relation matrix by using M groups of independent discovery results and corresponding importance weights, wherein the integrated relation matrix is marked as S, the scale of the integrated relation matrix is M multiplied by M, the integrated relation matrix is determined by the number of network nodes in the network G (V, E), and the matrix element S of the integrated relation matrix isα,βThe calculation method of (2) is shown in formula (4):
wherein,andrespectively representing network nodes v in the o-th group independent discovery resultαAnd vβThe community tag of (1), ifThenOtherwise
S62, for any element S in the integrated relation matrixα,βIf S isα,βIf > 0.5, the network node v is connectedαAnd vβBelonging to the same network community; if Sα,βIf the value is less than or equal to 0.5, the network node v is considered to be the network node vαAnd vβAnd finally, outputting the community label of each network node as a final result of the network community discovery method.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810373662.1A CN108712278A (en) | 2018-04-24 | 2018-04-24 | A kind of network community discovery method based on integrated study |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810373662.1A CN108712278A (en) | 2018-04-24 | 2018-04-24 | A kind of network community discovery method based on integrated study |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN108712278A true CN108712278A (en) | 2018-10-26 |
Family
ID=63867448
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810373662.1A Pending CN108712278A (en) | 2018-04-24 | 2018-04-24 | A kind of network community discovery method based on integrated study |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108712278A (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111726279A (en) * | 2020-05-28 | 2020-09-29 | 山西大学 | Community structure discovery method and system for electronic mail network |
| CN111756568A (en) * | 2020-05-06 | 2020-10-09 | 北京明略软件系统有限公司 | Method, device, computer storage medium and terminal for realizing community discovery |
| CN112598549A (en) * | 2020-12-23 | 2021-04-02 | 广东技术师范大学 | Learner potential overlapping community detection method, device, equipment and medium |
-
2018
- 2018-04-24 CN CN201810373662.1A patent/CN108712278A/en active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111756568A (en) * | 2020-05-06 | 2020-10-09 | 北京明略软件系统有限公司 | Method, device, computer storage medium and terminal for realizing community discovery |
| CN111726279A (en) * | 2020-05-28 | 2020-09-29 | 山西大学 | Community structure discovery method and system for electronic mail network |
| CN112598549A (en) * | 2020-12-23 | 2021-04-02 | 广东技术师范大学 | Learner potential overlapping community detection method, device, equipment and medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zhang et al. | Exact solution for mean first-passage time on a pseudofractal scale-free web | |
| Papadopoulos et al. | Network mapping by replaying hyperbolic growth | |
| US8634427B2 (en) | Method for identifying network similarity by matching neighborhood topology | |
| Orman et al. | Towards realistic artificial benchmark for community detection algorithms evaluation | |
| US10191998B1 (en) | Methods of data reduction for parallel breadth-first search over graphs of connected data elements | |
| CN111737535A (en) | Network characterization learning method based on element structure and graph neural network | |
| CN111309979B (en) | RDF Top-k query method based on neighbor vector | |
| CN111209410B (en) | Anchor point-based dynamic knowledge graph representation learning method and system | |
| CN105978711B (en) | A kind of best exchange side lookup method based on minimum spanning tree | |
| García-Pérez et al. | Precision as a measure of predictability of missing links in real networks | |
| CN108712278A (en) | A kind of network community discovery method based on integrated study | |
| CN109919172A (en) | A kind of clustering method and device of multi-source heterogeneous data | |
| CN112966165A (en) | Interactive community searching method and device based on graph neural network | |
| Šubelj | Label propagation for clustering | |
| CN116151384B (en) | Quantum circuit processing method and device and electronic equipment | |
| Levi et al. | A (centralized) local guide | |
| CN104657901A (en) | Community discovery method based on label propagation in random walk | |
| CN108198084A (en) | A kind of complex network is overlapped community discovery method | |
| CN113010813A (en) | Label propagation overlapping community discovery method and system based on random walk | |
| CN116611527B (en) | Quantum circuit processing method and device and electronic equipment | |
| CN109684185B (en) | Heuristic traversal-based big data processing capacity test method for supercomputer | |
| CN113034297A (en) | Complex network key node identification method and system based on node attraction | |
| CN115827996B (en) | Community query method and system with sharing constraint | |
| CN116151381B (en) | Quantum circuit processing method and device and electronic equipment | |
| Sarma et al. | Efficient random walk sampling in distributed networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20181026 |
|
| RJ01 | Rejection of invention patent application after publication |