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

Community discovery method based on iterative greedy thought

A technology for community discovery and thinking, applied in the field of complex network analysis, it can solve the problems of community quality differences, large time overhead, and complicated settings, and achieve the effects of quality improvement, low time overhead, and short running time.

Inactive Publication Date: 2018-11-16
SHANDONG UNIV +1
View PDF0 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

Although the meta-heuristic method has low dependence on the problem and has strong scalability, its shortcomings are also obvious: (1) There are many parameters and complex settings; (2) It takes a lot of time to analyze large and complex networks ; (3) Relying on prior information, that is, relying on the number or size of pre-set communities, the quality of communities generated by different pre-set information is quite different

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
  • Community discovery method based on iterative greedy thought
  • Community discovery method based on iterative greedy thought
  • Community discovery method based on iterative greedy thought

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0059] The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

[0060] Let the network G=(V,E). where V={v 1 ,v 2 ,...,v n} represents the set of nodes in the network, E={e 1 ,e 2 ,...,e l} represents the set of edges in the network. Given a community division, the modularity value corresponding to the division can be obtained. The modularity Q is calculated as follows:

[0061]

[0062] A ij Indicates the weight of the edge between node i and node j, d(i)=∑ j A ij Indicates the sum of edge weights connected to node i, c i Indicates the community to which node i belongs, and m indicates the sum of the weight values ​​of all edges in the network. if c i =c j , then δ(c i ,c j )=1; otherwise δ(c i ,c j )=0. The value range of modularity Q is between -0.5 and 1, and the closer the Q value is to 1, the higher the quality of the corresponding community division is.

[0063] Such as figure 1 As sho...

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 community discovery method based on an iterative greedy thought, and belongs to the field of complex network analysis. The method includes the specific steps that 1, communities are quickly merged based on the greedy thought so as to construct initial community partition; 2, a neighborhood of an initial solution is searched for a better solution through local search to further improve the solution quality; 3, the local optimal solution is disturbed, and nodes with a low contribution to the modularity value are initialized; 4, the distributed solution is reconstructed;5, a neighborhood of the reconstructed solution is searched for a better solution through local search to further improve the solution quality; 6, whether the newly generated solution is used in thenext iteration process or not is judged according to an acceptance criterion; 7, whether a stop condition is met or not is judged. The method is reasonable in design, has a strong global search capability, and can quickly and effectively obtain high-quality community division.

Description

technical field [0001] The invention belongs to the field of complex network analysis, and in particular relates to a community discovery method based on iterative greedy thought. Background technique [0002] In the real world, complex networks are usually a general term for various complex system networks in nature and human society, such as social networks, the World Wide Web, scientific citation networks, transportation networks, and biological protein interaction networks. The characteristics of community structure are usually included in complex networks, that is, the connections between nodes of the same type are dense and the connections between nodes of different types are sparse. How to detect community structure has become a hot research issue in the field of complex network analysis. The research on this issue is helpful for people to understand and predict the functions and characteristics of complex networks. In a social network such as Sina Weibo, if the inte...

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
IPC IPC(8): G06F17/30
Inventor 康钦马孔汉章李文全刘超王武闯邱会学
Owner SHANDONG 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