Laplacian matrix
આલેખ સિદ્ધાંતના ગાણિતિક ક્ષેત્રમાં, લેપલેસિયન મેટ્રિક્સ, જેને ગ્રાફ લેપલેસિયન, એડમિટન્સ મેટ્રિક્સ, કિર્ચોફ મેટ્રિક્સ અથવા ડિસ્ક્રીટ લેપલેસિયન પણ કહેવાય છે, તે આલેખની મેટ્રિક્સ રજૂઆત છે. પિયર-સિમોન લેપલેસ પરથી નામ અપાયેલા ગ્રાફ લેપલેસિયન મેટ્રિક્સને મર્યાદિત તફાવત પદ્ધતિ દ્વારા મેળવેલા નકારાત્મક સતત લેપલેસિયનના અંદાજિત ગ્રાફ પર નકારાત્મક સ્વતંત્ર લેપલેસ ઓપરેટરના મેટ્રિક્સ સ્વરૂપ તરીકે જોઈ શકાય છે. લેપલેસિયન મેટ્રિક્સ ગ્રાફના ઘણા ઉપયોગી ગુણધર્મો સાથે સંબંધિત છે. કિર્ચોફના પ્રમેય સાથે મળીને, તેનો ઉપયોગ આપેલ આલેખ માટે ફેલાયેલા વૃક્ષોની સંખ્યાની ગણતરી કરવા માટે થઈ શકે છે. ગ્રાફના સૌથી ઓછા કટને ફિડલર વેક્ટર દ્વારા અંદાજિત કરી શકાય છે-ગ્રાફ લેપલેસિયનના બીજા સૌથી નાના આઈગન વેલ્યુને અનુરૂપ આઈગનવેક્ટર-જે ચીગરની અસમાનતા દ્વારા સ્થાપિત થાય છે. લેપલેસિયન મેટ્રિક્સનું સ્પેક્ટ્રલ વિઘટન ઓછી પરિમાણીય એમ્બેડિંગ્સ બનાવવાની મંજૂરી આપે છે જે ઘણી મશીન લર્નિંગ એપ્લિકેશનોમાં દેખાય છે અને ગ્રાફ ડ્રોઇંગમાં સ્પેક્ટ્રલ લેઆઉટ નક્કી કરે છે. ગ્રાફ-આધારિત સંકેત પ્રક્રિયા ગ્રાફ ફોરિયર ટ્રાન્સફોર્મ પર આધારિત છે જે સિગ્નલને અનુરૂપ ગ્રાફના લેપલેસિયન મેટ્રિક્સના આઈગનવેક્ટર્સ માટે જટિલ સાઇનસોઈડ્સના પ્રમાણભૂત આધારને બદલીને પરંપરાગત સ્વતંત્ર ફોરિયર ટ્રાન્સફોર્મને વિસ્તરે છે. સરળ આલેખ માટે વ્યાખ્યાયિત કરવા માટે લેપલેસિયન મેટ્રિક્સ સૌથી સરળ છે, પરંતુ ધાર-ભારિત આલેખ માટેની એપ્લિકેશનોમાં વધુ સામાન્ય છે, એટલે કે, તેની ધાર પર વજન સાથે-ગ્રાફ સંલગ્નતા મેટ્રિક્સની એન્ટ્રીઓ. સ્પેક્ટ્રલ ગ્રાફ થિયરી ગ્રાફના ગુણધર્મોને સ્પેક્ટ્રમ સાથે સંબંધિત કરે છે, એટલે કે, આઈગનવેલ્યુઝ અને ગ્રાફ સાથે સંકળાયેલા મેટ્રિસીસના આઈગનવેક્ટર્સ, જેમ કે તેની નિકટતા મેટ્રિક્સ અથવા લેપલેસિયન મેટ્રિક્સ. અસંતુલિત વજન મેટ્રિક્સ સ્પેક્ટ્રમને અનિચ્છનીય રીતે અસર કરી શકે છે, જે સામાન્યીકરણની જરૂરિયાત તરફ દોરી જાય છે-મેટ્રિક્સ એન્ટ્રીઓની કોલમ/રો સ્કેલિંગ-પરિણામે સામાન્ય સંલગ્નતા અને લેપલેસિયન મેટ્રિક્સ થાય છે. સરળ આલેખ માટે વ્યાખ્યાઓ લેપલેસિયન મેટ્રિક્સ શિરોબિંદુઓ સાથેનો એક સરળ આલેખ આપવામાં આવે તો, તેના લેપલેસિયન મેટ્રિક્સને મેટ્રિક્સ દ્વારા તત્વ મુજબ અથવા સમકક્ષ રીતે વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં D એ ડિગ્રી મેટ્રિક્સ છે અને A એ ગ્રાફની નિકટતા મેટ્રિક્સ છે. એક સરળ આલેખ હોવાથી, તેમાં ફક્ત 1s અથવા 0s હોય છે અને તેના વિકર્ણ ઘટકો બધા 0s હોય છે. અહીં લેબલ થયેલ, દિશાહીન આલેખ અને તેના લેપલેસિયન મેટ્રિક્સનું સરળ ઉદાહરણ છે. આપણે દિશાહીન આલેખ માટે અવલોકન કરીએ છીએ કે નિકટતા મેટ્રિક્સ અને લેપલેસિયન મેટ્રિક્સ બંને સપ્રમાણ છે, અને લેપલેસિયન મેટ્રિક્સના પંક્તિ અને સ્તંભ-સરવાળા બધા શૂન્ય છે. નિર્દેશિત આલેખ માટે, નીચેના ઉદાહરણની જેમ, એપ્લિકેશનના આધારે ઇન્ડીગ્રી અથવા આઉટ ડિગ્રીનો ઉપયોગ કરી શકાય છેઃ નિર્દેશિત આલેખમાં, સંલગ્નતા મેટ્રિક્સ અને લેપલેસિયન મેટ્રિક્સ બંને અસમપ્રમાણ હોય છે. તેના લેપલેસિયન મેટ્રિક્સમાં, કૉલમ-સમ અથવા રો-સમ શૂન્ય હોય છે, જે તેના પર આધાર રાખે છે કે શું ઇન્ડીગ્રી અથવા આઉટ ડિગ્રીનો ઉપયોગ કરવામાં આવ્યો છે. ઇન્સિડેન્સ મેટ્રિક્સ દ્વારા સિમેટ્રિક લેપલેસિયન શિરોબિંદુ v અને ધાર e (શિરોબિંદુઓને જોડતા અને i> j સાથે) માટે તત્વ Bve સાથે ઇન્સિડેન્સ મેટ્રિક્સ B ને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. વૈકલ્પિક ઉત્પાદન કહેવાતા ધાર-આધારિત લેપલેસિયનને વ્યાખ્યાયિત કરે છે, જે નિર્દેશિત આલેખ માટે સામાન્ય રીતે ઉપયોગમાં લેવાતા શિરોબિંદુ-આધારિત લેપલેસિયન મેટ્રિક્સ એલ. સિમેટ્રિક લેપલેસિયનના વિરોધમાં છે. નિર્દેશિત આલેખનો લેપલેસિયન મેટ્રિક્સ વ્યાખ્યા દ્વારા સામાન્ય રીતે બિન-સિમેટ્રિક હોય છે, જ્યારે, દા. ત., પરંપરાગત સ્પેક્ટ્રલ ક્લસ્ટરિંગ મુખ્યત્વે સપ્રમાણ સંલગ્નતા અને લેપલેસિયન મેટ્રિક્સ સાથે દિશાહીન આલેખ માટે વિકસાવવામાં આવે છે. સમપ્રમાણતાની જરૂર હોય તેવી તકનીકોને લાગુ કરવા માટેનો એક તુચ્છ અભિગમ એ છે કે મૂળ નિર્દેશિત આલેખને દિશાહીન આલેખમાં ફેરવવો અને પછીના માટે લેપલેસિયન મેટ્રિક્સ બનાવવો. મેટ્રિક્સ નોટેશનમાં, દિશાહીન ગ્રાફના નિકટતા મેટ્રિક્સને, દા. ત., મૂળ નિર્દેશિત ગ્રાફ અને તેના મેટ્રિક્સ ટ્રાન્સપોઝના નિકટતા મેટ્રિક્સના બુલિયન સરવાળા તરીકે વ્યાખ્યાયિત કરી શકાય છે, જ્યાં શૂન્ય અને એક એન્ટ્રીઓને આંકડાકીય મૂલ્યોને બદલે તાર્કિક તરીકે ગણવામાં આવે છે, જેમ કે નીચેના ઉદાહરણમાંઃ લાપ્લેસીયન મેટ્રિક્સ નોર્મલાઇઝેશન મોટી ડિગ્રી સાથેનું શિરોબિંદુ, જેને હેવી નોડ પણ કહેવાય છે, તે મેટ્રિક્સ ગુણધર્મો પર પ્રભુત્વ ધરાવતા લાપ્લેસીયન મેટ્રિક્સમાં મોટી કર્ણ એન્ટ્રીમાં પરિણમે છે. સામાન્યીકરણનો ઉદ્દેશ લેપલેસિયન મેટ્રિક્સની એન્ટ્રીઓને શિરોબિંદુ ડિગ્રી દ્વારા વિભાજીત કરીને આવા શિરોબિંદુઓના પ્રભાવને અન્ય શિરોબિંદુઓની સમાન બનાવવાનો છે. શૂન્ય દ્વારા વિભાજન ટાળવા માટે, શૂન્ય ડિગ્રીવાળા અલગ શિરોબિંદુઓને સામાન્યકરણની પ્રક્રિયામાંથી બાકાત રાખવામાં આવે છે. સમમિતીય રીતે સામાન્યીકૃત લેપલેસિયન સમમિતીય રીતે સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ જ્યાં મૂરે-પેનરોઝ ઇન્વર્સ છે. આ રીતે ના ઘટકો દ્વારા આપવામાં આવે છે સમપ્રમાણતાથી સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સ સમપ્રમાણ હોય છે જો અને માત્ર ત્યારે જ જો સંલગ્નતા મેટ્રિક્સ સમપ્રમાણ હોય. નિર્દેશિત આલેખના બિન-સમમિતીય સંલગ્નતા મેટ્રિક્સ માટે, સામાન્યીકરણ માટે અનિર્ણિત અને બાહ્ય ડિગ્રીનો ઉપયોગ કરી શકાય છેઃ ડાબે (રેન્ડમ-વોક) અને જમણે સામાન્યીકૃત લેપલેસિયન ડાબે (રેન્ડમ-વોક) સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ જ્યાં મૂરે-પેનરોઝ વ્યસ્ત છે. ના ઘટકો દ્વારા આપવામાં આવે છે એ જ રીતે, યોગ્ય સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. જો સંલગ્નતા મેટ્રિક્સ સપ્રમાણ હોય તો ડાબી કે જમણી સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સ સપ્રમાણ નથી, સિવાય કે તમામ અલગ-અલગ શિરોબિંદુઓના તુચ્છ કેસ. ઉદાહરણ તરીકે, ઉદાહરણ એ પણ દર્શાવે છે કે જો કોઈ અલગ શિરોબિંદુ ન હોય, તો જમણી બાજુએ સ્ટોકેસ્ટિક હોય છે અને તેથી તે રેન્ડમ વોકનું મેટ્રિક્સ છે, જેથી ડાબી બાજુએ નોર્મલાઇઝ્ડ લેપલેસિયનમાં દરેક હરોળનો સરવાળો શૂન્ય થાય છે. આમ આપણે કેટલીકવાર વૈકલ્પિક રીતે રેન્ડમ-વોક નોર્મલાઇઝ્ડ લેપલેસિયન કહીએ છીએ. ઓછા અસામાન્ય રીતે ઉપયોગમાં લેવાતા જમણા સામાન્યીકૃત લેપલેસિયનમાં દરેક સ્તંભનો સરવાળો શૂન્ય થાય છે કારણ કે તે ડાબી બાજુએ સ્ટોકેસ્ટિક હોય છે. નિર્દેશિત આલેખના બિન-સમમિતીય સંલગ્નતા મેટ્રિક્સ માટે, સામાન્યીકરણ માટે અનિર્ણિત અથવા આઉટ ડિગ્રી પણ પસંદ કરવાની જરૂર છેઃ પંક્તિ-સમ સાથે ડાબી બાજુની સામાન્યીકૃત લાપ્લેસીયન તમામ 0 જમણી સ્ટોકેસ્ટિક સાથે સંબંધિત છે, જ્યારે જમણી બાજુની સામાન્યીકૃત લેપ્લેસીયન સ્તંભ-સમ સાથે તમામ 0 ડાબી સ્ટોકેસ્ટિક ધરાવે છે. ભારિત ધારવાળા આલેખ માટેની વ્યાખ્યાઓ ભારિત ધારવાળા આલેખમાં સામાન્ય રીતે તેમની નિકટતા મેટ્રિક્સ દ્વારા સરળતાથી વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં એન્ટ્રીઓના મૂલ્યો આંકડાકીય હોય છે અને હવે શૂન્ય અને એક સુધી મર્યાદિત નથી. સ્પેક્ટ્રલ ક્લસ્ટરિંગ અને ગ્રાફ-આધારિત સિગ્નલ પ્રોસેસિંગમાં, જ્યાં ગ્રાફ શિરોબિંદુઓ ડેટા બિંદુઓનું પ્રતિનિધિત્વ કરે છે, ત્યાં ધાર વજનની ગણતરી કરી શકાય છે, દા. ત., ડેટા બિંદુઓની જોડી વચ્ચેના અંતરના વ્યસ્ત પ્રમાણમાં, જે તમામ વજનને બિન-નકારાત્મક બનવા તરફ દોરી જાય છે. ડેટા બિંદુઓ વચ્ચે સહસંબંધ અને વિરોધી સહસંબંધનો ઉપયોગ સ્વાભાવિક રીતે હકારાત્મક અને નકારાત્મક બંને વજન તરફ દોરી જાય છે. સરળ આલેખ માટેની મોટાભાગની વ્યાખ્યાઓ બિન-નકારાત્મક વજનના પ્રમાણભૂત કિસ્સામાં તુચ્છ રીતે વિસ્તૃત કરવામાં આવે છે, જ્યારે નકારાત્મક વજન પર વધુ ધ્યાન આપવાની જરૂર હોય છે, ખાસ કરીને સામાન્યીકરણમાં. લાપ્લેસીયન મેટ્રિક્સ લાપ્લેસીયન મેટ્રિક્સને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે કે જ્યાં D એ ડિગ્રી મેટ્રિક્સ છે અને A એ ગ્રાફની નિકટતા મેટ્રિક્સ છે. નિર્દેશિત આલેખ માટે, એપ્લિકેશનના આધારે ઇન્ડીગ્રી અથવા આઉટ ડિગ્રીનો ઉપયોગ કરી શકાય છે, જેમ કે નીચેના ઉદાહરણમાંઃ ગ્રાફ સ્વ-લૂપ્સ, જે સંલગ્નતા મેટ્રિક્સના મુખ્ય કર્ણ પર બિન-શૂન્ય એન્ટ્રીઓ દ્વારા પોતાને પ્રગટ કરે છે, તેને મંજૂરી છે પરંતુ ગ્રાફ લેપલેસિયન મૂલ્યોને અસર કરતા નથી. ઇન્સિડેન્સ મેટ્રિક્સ દ્વારા સિમેટ્રિક લેપલેસિયન ભારિત ધારવાળા આલેખ માટે કોઈ ભારિત ઇન્સિડેન્સ મેટ્રિક્સ B ને વ્યાખ્યાયિત કરી શકે છે અને તેનો ઉપયોગ અનુરૂપ સપ્રમાણ લેપલેસિયનને આ રીતે બનાવવા માટે કરી શકે છે. અહીં વર્ણવેલ વૈકલ્પિક સ્વચ્છ અભિગમ, જોડાણથી વજનને અલગ કરવાનો છેઃ નિયમિત આલેખ માટે ઇન્સિડેન્સ મેટ્રિક્સનો ઉપયોગ કરવાનું ચાલુ રાખો અને માત્ર વજનના મૂલ્યોને ધારણ કરતો મેટ્રિક્સ રજૂ કરો. સ્પ્રિંગ સિસ્ટમ એ આ મોડેલનું એક ઉદાહરણ છે જેનો ઉપયોગ મિકેનિક્સમાં આપેલ કઠોરતા અને એકમ લંબાઈના ઝરણાઓની પ્રણાલીનું વર્ણન કરવા માટે થાય છે, જ્યાં કઠોરતાના મૂલ્યો ગ્રાફ ધારના વજનની ભૂમિકા ભજવે છે. આમ આપણે ભારરહિત ઇન્સિડેન્સ મેટ્રિક્સ B ની વ્યાખ્યાનો ફરીથી ઉપયોગ શિરોબિંદુ v અને ધાર e (શિરોબિંદુઓને જોડતા અને i> j સાથે) માટે તત્વ Bve સાથે કરીએ છીએ. B ની વ્યાખ્યામાં ધાર તકનીકી રીતે નિર્દેશિત હોવા છતાં, તેમની દિશાઓ મનસ્વી હોઈ શકે છે, તેમ છતાં તે જ સપ્રમાણ લેપલેસિયન મેટ્રિક્સ L માં પરિણમે છે જ્યાં B નું મેટ્રિક્સ ટ્રાન્સપોઝ છે. બાંધકામને નીચેના ઉદાહરણમાં સચિત્ર કરવામાં આવ્યું છે, જ્યાં દરેક ધારને વજન મૂલ્ય i સોંપવામાં આવ્યું છે, નિર્દેશિત આલેખ માટે સમપ્રમાણ લેપલેસિયન સાથે. સરળ આલેખની જેમ, નિર્દેશિત ભારિત આલેખનું લેપલેસિયન મેટ્રિક્સ વ્યાખ્યા દ્વારા સામાન્ય રીતે બિન-સમપ્રમાણ હોય છે. લેપલેસિયનનું નિર્માણ કરતા પહેલા મૂળ નિર્દેશિત આલેખને દિશાહીન આલેખમાં ફેરવીને સમપ્રમાણતા લાગુ કરી શકાય છે. દિશાહીન આલેખની નિકટતા મેટ્રિક્સને, દા. ત., મૂળ નિર્દેશિત આલેખની નિકટતા મેટ્રિક્સના સરવાળા તરીકે વ્યાખ્યાયિત કરી શકાય છે અને તેના મેટ્રિક્સને નીચે આપેલા ઉદાહરણની જેમ સ્થાનાંતરિત કરી શકાય છેઃ જ્યાં શૂન્ય અને એક એન્ટ્રીઓને સરળ આલેખ, મૂલ્યો માટે તાર્કિકને બદલે આંકડાકીય તરીકે ગણવામાં આવે છે, પરિણામોમાં તફાવત સમજાવીને-સરળ આલેખ માટે, સમપ્રમાણિત આલેખ હજુ પણ તેના સમપ્રમાણિત નિકટતા મેટ્રિક્સ સાથે માત્ર તાર્કિક, આંકડાકીય મૂલ્યો સાથે સરળ હોવો જરૂરી છે, દા. ત., તાર્કિક સરવાળો 1 v1 = 1 છે, જ્યારે આંકડાકીય સરવાળો 1 + 1 = 2 છે. વૈકલ્પિક રીતે, સપ્રમાણ લેપલેસિયન મેટ્રિક્સની ગણતરી બે લેપલેસિયનમાંથી ઇન્ડેગ્રી અને આઉટ ડિગ્રીનો ઉપયોગ કરીને કરી શકાય છે, જેમ કે નીચેના ઉદાહરણમાં છેઃ આઉટ-ડિગ્રી લેપલેસિયન ટ્રાન્સપોઝ્ડ અને ઇન-ડિગ્રી લેપલેસિયનનો સરવાળો સપ્રમાણ લેપલેસિયન મેટ્રિક્સ બરાબર છે. લાપ્લેસીયન મેટ્રિક્સ નોર્મલાઇઝેશન નોર્મલાઇઝેશનનો ધ્યેય, સરળ આલેખની જેમ, લેપ્લેસીયન મેટ્રિક્સની વિકર્ણ એન્ટ્રીઓને તમામ એકમ બનાવવાનો છે, જે અનુરૂપ રીતે વિકર્ણ એન્ટ્રીઓને પણ સ્કેલ કરે છે. ભારિત આલેખમાં, શિરોબિંદુ મોટી માત્રામાં હોઈ શકે છે કારણ કે તેમાં થોડી સંખ્યામાં જોડાયેલી ધાર હોય છે પરંતુ મોટા વજન સાથે તેમજ એકમ વજન સાથે મોટી સંખ્યામાં જોડાયેલી ધાર હોય છે. ગ્રાફ સ્વ-લૂપ્સ, એટલે કે, સંલગ્નતા મેટ્રિક્સના મુખ્ય કર્ણ પર બિન-શૂન્ય એન્ટ્રીઓ, ગ્રાફ લેપલેસિયન મૂલ્યોને અસર કરતી નથી, પરંતુ સામાન્યકરણ પરિબળોની ગણતરી માટે તેને ગણવાની જરૂર પડી શકે છે. સમમિતીય રીતે સામાન્યીકૃત લેપલેસિયન સમમિતીય રીતે સામાન્યીકૃત લેપલેસિયનને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં L એ બિનપરંપરાગત લેપલેસિયન છે, A એ સંલગ્નતા મેટ્રિક્સ છે, D એ ડિગ્રી મેટ્રિક્સ છે, અને તે મૂરે-પેનરોઝ ઇન્વર્સ છે. ડિગ્રી મેટ્રિક્સ D વિકર્ણ હોવાથી, તેનું પારસ્પરિક વર્ગમૂળ માત્ર વિકર્ણ મેટ્રિક્સ છે, જેની વિકર્ણ એન્ટ્રીઓ D ની વિકર્ણ એન્ટ્રીઓના વર્ગમૂળના પારસ્પરિક છે. જો તમામ ધાર વજન બિન-નકારાત્મક હોય તો તમામ ડિગ્રી મૂલ્યો આપમેળે પણ બિન-નકારાત્મક હોય છે અને તેથી દરેક ડિગ્રી મૂલ્યમાં અનન્ય હકારાત્મક વર્ગમૂળ હોય છે. શૂન્ય દ્વારા વિભાજનને ટાળવા માટે, શૂન્ય ડિગ્રીવાળા શિરોબિંદુઓને સામાન્યીકરણની પ્રક્રિયામાંથી બાકાત રાખવામાં આવે છે, જેમ કે નીચેના ઉદાહરણમાંઃ સમપ્રમાણતાવાળા સામાન્યીકૃત લેપલેસિયન એક સમપ્રમાણિત મેટ્રિક્સ છે જો અને માત્ર ત્યારે જ જો સંલગ્નતા મેટ્રિક્સ A સમપ્રમાણ હોય અને D ની કર્ણ એન્ટ્રીઓ બિન-નકારાત્મક હોય, તો આ કિસ્સામાં આપણે સમપ્રમાણિત સામાન્યીકૃત લેપલેસિયન શબ્દનો ઉપયોગ કરી શકીએ છીએ. સપ્રમાણ સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સને વજનહીન ઇન્સિડેન્સ મેટ્રિક્સ B અને કર્ણ મેટ્રિક્સ W નો ઉપયોગ કરીને પણ લખી શકાય છે, જેમાં ધાર વજન હોય છે અને નવા ભારિત ઇન્સિડેન્સ મેટ્રિક્સને વ્યાખ્યાયિત કરી શકાય છે, જેમની પંક્તિઓ શિરોબિંદુઓ દ્વારા અનુક્રમિત થાય છે અને જેમના સ્તંભો G ની ધાર દ્વારા અનુક્રમિત થાય છે, જેમ કે e = {u, v} ધારને અનુરૂપ દરેક સ્તંભમાં u ને અનુરૂપ હરોળમાં એન્ટ્રી હોય છે, જે v ને અનુરૂપ હરોળમાં એન્ટ્રી હોય છે અને તેમાં અન્યત્ર 0 એન્ટ્રી હોય છે. રેન્ડમ વોક નોર્મલાઇઝ્ડ લેપલેસિયન રેન્ડમ વોક નોર્મલાઇઝ્ડ લેપલેસિયનને વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં D એ ડિગ્રી મેટ્રિક્સ છે. ડિગ્રી મેટ્રિક્સ D વિકર્ણ હોવાથી, તેનો વ્યુત્ક્રમ ફક્ત વિકર્ણ મેટ્રિક્સ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જેમાં વિકર્ણ એન્ટ્રીઓ હોય છે જે D ની અનુરૂપ વિકર્ણ એન્ટ્રીઓના પારસ્પરિક હોય છે. અલગ શિરોબિંદુઓ (ડિગ્રી 0 સાથે) માટે, એક સામાન્ય પસંદગી અનુરૂપ તત્વને 0 પર સેટ કરવાની હોય છે. રેન્ડમ-વોક નોર્મલાઇઝ્ડ લેપલેસિયનનું નામ એ હકીકત પરથી આવે છે કે આ મેટ્રિક્સ છે, જ્યાં બિન-નકારાત્મક વજન ધારીને ગ્રાફ પર રેન્ડમ વૉકરનું સંક્રમણ મેટ્રિક્સ છે. ઉદાહરણ તરીકે, ચાલો i-th પ્રમાણભૂત બેસિસ વેક્ટરને દર્શાવીએ. પછી એક સંભાવના વેક્ટર છે જે શિરોબિંદુથી એક પગલું લીધા પછી રેન્ડમ વૉકરના સ્થાનોના વિતરણનું પ્રતિનિધિત્વ કરે છે; એટલે કે. વધુ સામાન્ય રીતે, જો વેક્ટર ગ્રાફના શિરોબિંદુઓ પર રેન્ડમ વૉકરના સ્થાનનું સંભાવના વિતરણ હોય, તો તે પગલાં પછી વૉકરનું સંભાવના વિતરણ છે. રેન્ડમ વોક નોર્મલાઇઝ્ડ લેપલેસિયનને લેફ્ટ નોર્મલાઇઝ્ડ લેપલેસિયન પણ કહી શકાય કારણ કે નોર્મલાઇઝેશન ડાબી બાજુના નોર્મલાઇઝેશન મેટ્રિક્સ દ્વારા લેપલેસિયનને ગુણાકાર કરીને કરવામાં આવે છે. તેમાં દરેક પંક્તિનો સરવાળો શૂન્ય છે કારણ કે તે યોગ્ય સ્ટોકેસ્ટિક છે, એમ ધારીને કે તમામ વજન બિન-નકારાત્મક છે. ઓછા અસામાન્ય રીતે ઉપયોગમાં લેવાતા જમણા સામાન્યીકૃત લેપલેસિયનમાં દરેક સ્તંભનો સરવાળો શૂન્ય થાય છે કારણ કે તે ડાબી બાજુએ સ્ટોકેસ્ટિક હોય છે. નિર્દેશિત આલેખના બિન-સમમિતીય સંલગ્નતા મેટ્રિક્સ માટે, સામાન્યીકરણ માટે અનિર્ણિત અથવા આઉટ ડિગ્રી પણ પસંદ કરવાની જરૂર છેઃ પંક્તિ-સમ સાથે ડાબી બાજુની સામાન્યીકૃત લાપ્લેસીયન તમામ 0 જમણી સ્ટોકેસ્ટિક સાથે સંબંધિત છે, જ્યારે જમણી બાજુની સામાન્યીકૃત લેપ્લેસીયન સ્તંભ-સમ સાથે તમામ 0 ડાબી સ્ટોકેસ્ટિક ધરાવે છે. નકારાત્મક વજન નકારાત્મક વજન સામાન્યીકરણ માટે ઘણા પડકારો રજૂ કરે છેઃ નકારાત્મક વજનની હાજરી કુદરતી રીતે શૂન્ય પંક્તિ-અને/અથવા બિન-અલગ શિરોબિંદુઓ માટે સ્તંભ-રકમમાં પરિણમી શકે છે. હકારાત્મક વજનની મોટી પંક્તિ-સરવાળો અને નકારાત્મક વજનની સમાન નકારાત્મક મોટી પંક્તિ-સરવાળો ધરાવતું શિરોબિંદુ, એકસાથે શૂન્ય સુધી સરવાળો કરે છે, તેને ભારે નોડ ગણી શકાય અને બંને મોટા મૂલ્યોને માપવામાં આવે છે, જ્યારે વિકર્ણ પ્રવેશ શૂન્ય રહે છે, જેમ કે અલગ શિરોબિંદુ માટે. નકારાત્મક વજન નકારાત્મક પંક્તિ-અને/અથવા સ્તંભ-સરવાળો પણ આપી શકે છે, જેથી બિન-સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સમાં અનુરૂપ કર્ણ પ્રવેશ નકારાત્મક હશે અને સપ્રમાણ સામાન્યીકરણ માટે જરૂરી હકારાત્મક વર્ગમૂળ અસ્તિત્વમાં રહેશે નહીં. સામાન્યીકરણના હેતુ માટે પંક્તિ-અને/અથવા સ્તંભ-સરવાળાનું સંપૂર્ણ મૂલ્ય લેવા માટે દલીલો કરી શકાય છે, આમ સંભવિત મૂલ્ય-1 ને સામાન્યીકૃત લેપલેસિયન મેટ્રિક્સના મુખ્ય કર્ણની કાયદેસર એકમ એન્ટ્રી તરીકે ગણવામાં આવે છે. ગુણધર્મો (દિશાહીન) આલેખ G અને તેના લાપ્લેસીયન મેટ્રિક્સ L માટે આઈગનવેલ્યુ સાથેઃ L સમપ્રમાણ છે. L એ હકારાત્મક-સમાન છે (તે બધા માટે છે). આ એ હકીકત પરથી જોઈ શકાય છે કે લેપલેસિયન સમપ્રમાણ અને ત્રાંસા રીતે પ્રબળ છે. એલ એ એમ-મેટ્રિક્સ છે (તેની ઓફ-ડાયાગોનલ એન્ટ્રીઓ નોન-પોઝિટિવ છે, તેમ છતાં તેના આઈગનવેલ્યુના વાસ્તવિક ભાગો નોન-નેગેટિવ છે). L નો દરેક પંક્તિનો સરવાળો અને સ્તંભનો સરવાળો શૂન્ય છે. ખરેખર, સરવાળામાં, શિરોબિંદુની માત્રાનો સરવાળો દરેક પાડોશી માટે "-1" સાથે કરવામાં આવે છે. પરિણામે, કારણ કે વેક્ટર સંતુષ્ટ કરે છે આ એ પણ સૂચવે છે કે લેપલેસિયન મેટ્રિક્સ એકવચન છે. આલેખમાં જોડાયેલા ઘટકોની સંખ્યા એ લાપ્લેસીયનના નલસ્પેસનું પરિમાણ અને 0 આઈગન વેલ્યુની બીજગણિત ગુણાકાર છે. L ની સૌથી નાની બિન-શૂન્ય આઈગન વેલ્યુને સ્પેક્ટ્રલ ગેપ કહેવામાં આવે છે. L નું બીજું સૌથી નાનું આઈગન વેલ્યુ (શૂન્ય હોઈ શકે છે) એ G નું બીજગણિત જોડાણ (અથવા ફિડલર મૂલ્ય) છે અને ગ્રાફના સૌથી ઓછા કટનો અંદાજ કાઢે છે. લાપ્લેસીયન એ કાર્યોના n-પરિમાણીય વેક્ટર જગ્યા પર એક સંચાલક છે, જ્યાં G નો શિરોબિંદુ સમૂહ છે, અને. જ્યારે G એ k-રેગ્યુલર હોય, ત્યારે નોર્મલાઇઝ્ડ લેપલેસિયન છેઃ, જ્યાં A એ સંલગ્નતા મેટ્રિક્સ છે અને I એ ઓળખ મેટ્રિક્સ છે. બહુવિધ જોડાયેલા ઘટકોવાળા આલેખ માટે, L એ બ્લોક કર્ણ મેટ્રિક્સ છે, જ્યાં દરેક બ્લોક દરેક ઘટક માટે સંબંધિત લેપલેસિયન મેટ્રિક્સ છે, સંભવતઃ શિરોબિંદુઓને ફરીથી ગોઠવ્યા પછી (એટલે કે. L એ ક્રમચય છે-બ્લોક કર્ણ મેટ્રિક્સ જેવું જ). લેપલેસિયન મેટ્રિક્સ L નું ટ્રેસ એ ગણવામાં આવેલા ગ્રાફની ધારની સંખ્યા ક્યાં છે તેની બરાબર છે. હવે એકમ-સામાન્ય આઈગનવેક્ટર્સ અને અનુરૂપ આઈગનવેલ્યુઓ સાથે આઈગનડેકમ્પોઝિશનને ધ્યાનમાં લોઃ કારણ કે તેને પોતાની સાથે વેક્ટરના આંતરિક ઉત્પાદન તરીકે લખી શકાય છે, આ દર્શાવે છે કે અને તેથી તેના આઈગનવેલ્યુઓ બધા બિન-નકારાત્મક છે. સામાન્યીકૃત સમપ્રમાણ લેપલેસિયનના તમામ આઈગન મૂલ્યો 0 = μ0 ≤. ≤ μn − 1 ≤ 2 ને સંતોષે છે. આ આઈગન વેલ્યુઓ (સામાન્યીકૃત લેપલેસિયનના વર્ણપટ તરીકે ઓળખાય છે) સામાન્ય આલેખ માટે અન્ય આલેખ અચળાંક સાથે સારી રીતે સંબંધિત છે. કોઈ તપાસી શકે છે કેઃ, એટલે કે, સામાન્યીકૃત લેપલેસિયન જેવું જ છે. આ કારણોસર, જો તે સામાન્ય રીતે સપ્રમાણ ન હોય તો પણ, તેમાં વાસ્તવિક આઈગનવેલ્યુ હોય છે-જે સામાન્યીકૃત સપ્રમાણ લેપલેસિયનના આઈગનવેલ્યુ જેવું જ હોય છે. ગ્રાફ લાપ્લેસીયન મેટ્રિક્સને આગળ મર્યાદિત તફાવત પદ્ધતિ દ્વારા મેળવેલા નકારાત્મક સતત લાપ્લેસીયન ઓપરેટરને અંદાજિત કરતા ગ્રાફ પર નકારાત્મક સ્વતંત્ર લાપ્લેસ ઓપરેટરના મેટ્રિક્સ સ્વરૂપ તરીકે જોઈ શકાય છે. (ડિસ્ક્રીટ પોઈસન સમીકરણ જુઓ) આ અર્થઘટનમાં, દરેક આલેખ શિરોબિંદુને ગ્રીડ બિંદુ તરીકે ગણવામાં આવે છે; શિરોબિંદુની સ્થાનિક જોડાણ આ ગ્રીડ બિંદુ પર મર્યાદિત તફાવત અંદાજ સ્ટેન્સિલ નક્કી કરે છે, ગ્રીડનું કદ હંમેશા દરેક ધાર માટે એક હોય છે, અને કોઈપણ ગ્રીડ બિંદુઓ પર કોઈ અવરોધો નથી, જે સજાતીય ન્યુમેન સીમા સ્થિતિ, એટલે કે મુક્ત સીમાને અનુરૂપ હોય છે. આવા અર્થઘટન, ઉદાહરણ તરીકે, અનંત સંખ્યામાં શિરોબિંદુઓ અને ધાર સાથે ગ્રાફના કિસ્સામાં લાપ્લેસીયન મેટ્રિક્સને સામાન્ય બનાવવાની મંજૂરી આપે છે, જે અનંત કદના લાપ્લેસીયન મેટ્રિક્સ તરફ દોરી જાય છે. લાપ્લેસીયન મેટ્રિક્સના સામાન્યીકરણ અને વિસ્તરણ સામાન્યીકૃત લેપ્લેસીયનને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ નોંધ લો કે સામાન્ય લેપ્લેસીયન એક સામાન્યીકૃત લેપ્લેસીયન છે. નિકટતા મેટ્રિક્સની ચુંબકીય લેપલેસિયન એન્ટ્રીઓ જટિલ-મૂલ્યવાન હોઈ શકે છે, આ કિસ્સામાં મેટ્રિક્સ સમપ્રમાણતાની કલ્પનાને હર્મિશિયન મેટ્રિક્સ સાથે બદલવાની જરૂર છે. વાસ્તવિક વજન સાથે નિર્દેશિત આલેખ માટે ચુંબકીય લેપલેસિયનનું નિર્માણ જટિલ એન્ટ્રીઓ સાથે સમપ્રમાણિત લેપલેસિયન અને હર્મિશિયન ફેઝ મેટ્રિક્સના વાસ્તવિક સમપ્રમાણ મેટ્રિક્સના હેડામર્ડ પ્રોડક્ટ તરીકે કરવામાં આવે છે, જે જટિલ સમતલમાં ફેઝમાં ધારની દિશાને એન્કોડ કરે છે. ક્વોન્ટમ ભૌતિકશાસ્ત્રના સંદર્ભમાં, ચુંબકીય લેપલેસિયનને એવા સંચાલક તરીકે અર્થઘટન કરી શકાય છે જે આલેખ પર મુક્ત ચાર્જ કણની ઘટનાનું વર્ણન કરે છે, જે ચુંબકીય ક્ષેત્રની ક્રિયાને આધિન છે અને પરિમાણને વિદ્યુત ચાર્જ કહેવામાં આવે છે. નીચેના ઉદાહરણમાંઃ વિકૃત લેપલેસિયન વિકૃત લેપલેસિયનને સામાન્ય રીતે વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં I એ ઓળખ મેટ્રિક્સ છે, A એ નિકટતા મેટ્રિક્સ છે, D એ ડિગ્રી મેટ્રિક્સ છે, અને s એ (જટિલ-મૂલ્ય) સંખ્યા છે. પ્રમાણભૂત લેપલેસિયન ન્યાયી છે અને સંકેત વિનાનું લેપલેસિયન છે. સંકેતહીન લેપલેસિયનને ડિગ્રી મેટ્રિક્સ ક્યાં છે તે રીતે વ્યાખ્યાયિત કરવામાં આવે છે, અને તે સંલગ્ન મેટ્રિક્સ છે. હસ્તાક્ષરિત લેપલેસિયનની જેમ, સંકેતહીન લેપલેસિયન પણ હકારાત્મક અર્ધ-નિશ્ચિત છે કારણ કે તેને ઇન્સિડેન્સ મેટ્રિક્સ ક્યાં છે તે રીતે પરિબળ બનાવી શકાય છે. તેમાં 0-આઈગનવેક્ટર હોય છે જો અને માત્ર ત્યારે જ જો તેમાં અલગ શિરોબિંદુઓ સિવાય અન્ય દ્વિપક્ષી જોડાયેલ ઘટક હોય. આને આ રીતે દર્શાવી શકાય છે આ એક ઉકેલ છે જ્યાં જો અને માત્ર ત્યારે જ જો આલેખમાં દ્વિપક્ષી જોડાયેલ ઘટક હોય. નિર્દેશિત મલ્ટીગ્રાફ્સ લાપ્લેસીયન મેટ્રિક્સના એનાલોગને નિર્દેશિત મલ્ટીગ્રાફ્સ માટે વ્યાખ્યાયિત કરી શકાય છે. આ કિસ્સામાં લાપ્લેસીયન મેટ્રિક્સ L ને એ રીતે વ્યાખ્યાયિત કરવામાં આવે છે કે જ્યાં D એ Di સાથે વિકર્ણ મેટ્રિક્સ છે, i એ શિરોબિંદુ i ની બહારની ડિગ્રીની બરાબર છે અને A એ AI સાથે મેટ્રિક્સ છે, j એ i થી j (લૂપ્સ સહિત) ની ધારની સંખ્યાની બરાબર છે. ઓપન સોર્સ સોફ્ટવેર અમલીકરણ સાયપી નેટવર્કએક્સ જુલિયા એપ્લિકેશન સોફ્ટવેર સ્કિકિટ-લર્ન સ્પેક્ટ્રલ ક્લસ્ટરિંગ પાયજીએસપીઃ પાયથોન મેગામેનમાં ગ્રાફ સિગ્નલ પ્રોસેસિંગઃ લાખો પોઇંટ્સ માટે મેનિફોલ્ડ લર્નિંગ સરળજી ડાયનેમિક ગ્રાફ માટે લેપલેસિયન ચેન્જ પોઇન્ટ ડિટેક્શન (કેડીડી 2020) લેપલેસિયનઓપ્ટ (લેપલેસિયનના વજનવાળા ગ્રાફના બીજા આઈગનવેલ્યુને મહત્તમ કરવા માટે જુલિયા પેકેજ) લિગએમજી (મોટા અનિયમિત ગ્રાફ મલ્ટીગ્રિડ) Laplacians.jl મર્યાદિત વજનવાળા ગ્રાફ પર સ્ટિફનેસ મેટ્રિક્સ અંતર સંક્રમણ દર મેટ્રિક્સ ગણતરીઓ જુઓ