Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Method and device for calculating quality measure index of overlapping community set

A technology of quality measurement and overlapping communities, applied in the computer field, can solve problems such as inapplicable calculation of quality metrics for large-scale community collections

Active Publication Date: 2018-11-27
SHENZHEN UNIV
View PDF9 Cites 1 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0003] The main purpose of the present invention is to provide a method and device for calculating the quality metrics of overlapping community sets, aiming at solving the technical problem that existing algorithms are not suitable for the calculation of large-scale community set quality metrics

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method and device for calculating quality measure index of overlapping community set
  • Method and device for calculating quality measure index of overlapping community set
  • Method and device for calculating quality measure index of overlapping community set

Examples

Experimental program
Comparison scheme
Effect test

no. 1 example

[0061] There are two existing calculation methods for calculating the set quality metrics of overlapping communities, including mutul3 (algorithm designed by the proposer of NMI_LFK) and onmi (algorithm designed by the proposer of NMI_MAX). mutul3 can calculate NMI_LFK, and onmi can calculate NMI_LFK and NMI_MAX at the same time. But these algorithms are all serial calculations. Based on this, the present invention proposes a new calculation method MPI-POCMC (MPI-Parallel Overlapping CommunityMetric Computation, a parallel community metric calculation based on the MPI standard), which is a parallel distributed framework algorithm. Compared with existing algorithms, the calculation method of the present invention is faster.

[0062] The flow chart of the calculation method of the non-overlapping community set quality metrics provided by the first embodiment of the present invention can be found in figure 1 , including:

[0063] Step 1. Obtain community set X={X 1 ,X 2 ,...X...

no. 2 example

[0091] The first kind of overlapping community set quality metric index calculation device provided by the present invention can be found in image 3 As shown, it includes a processor 301, a memory 302 and a communication bus 303, wherein:

[0092] The communication bus 303 is used to realize the connection communication between the processor 301 and the memory 302;

[0093] The processor 301 is configured to execute the community set quality metric index calculation program stored in the memory 302, and the community set quality metric index calculation program includes:

[0094] The acquisition module is used to acquire the community set X={X 1 ,X 2 ,...,X K}, Y={Y 1 ,Y 2 ,...,Y K'}, and the vertex set V={v including each community in the community set X and Y 1 ,v 2 ,...,v n}; Described K, K', n represent the number of elements in community set X, Y and vertex set V respectively;

[0095] A processing module, for according to the vertex set V={v 1 ,v 2 ,...,v n...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a method and device for calculating a quality measure index of an overlapping community set. The method includes: obtaining a vertex set V by acquiring elements in each community in community sets X and Y, traversing the community sets X and Y, recording tags of communities to which each vertex vi belongs in the community sets X and Y, and obtaining tag sets ListXid [i] andListYid [i]; constructing a community tag Cartesian product data set DicList [i] of each vertex; obtaining a community tag data set ListXid; segmenting and distributing elements in the ListXid set toeach process on the basis of a greedy algorithm and load balancing; allowing each process to perform operation to obtain a required value for calculation of each index; and finally merging related values of all the indexes into a single process for operation, and obtaining measure indexes of the community sets X and Y. The method adopts a parallel distributed computing framework MPICH and same community tag pair counting to speed up the operation of community set quality measure indexes. The method for calculating the quality measure index of the overlapping community set can calculate out quality measure indexes, and is suitable for calculation of the quality measure indexes of the large-scale overlapping communities.

Description

technical field [0001] The invention belongs to the field of computer technology, and in particular relates to a method and device for calculating a quality metric index of an overlapping community set. Background technique [0002] In general, a social network graph can be abstracted as a collection of nodes and edges, where nodes represent individuals in the network, and edges represent certain associations between individuals and individuals. The social network graph has a community structure, in which the community is composed of tightly connected nodes in the network graph, and the communities are connected by sparse nodes. Community discovery is to describe and divide the community structure of a network, and the result of community discovery is called community set. If the nodes in the community set belong to only one community, the community set is called a non-overlapping community set, otherwise it is called an overlapping community set. It should be understood t...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06Q10/06G06Q50/00
CPCG06Q10/06393G06Q50/01
Inventor 冯禹洪吴远诗佘松罗秋明
Owner SHENZHEN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com